[java] zoeken in linkedlist

[Verwijderd]

Hallo,

ik heb een applicatie die recursief mijn hardeschijf afzoekt naar bestanden met een opgegeven extensie. deze methode zet alle filenames in een linkedlist. dit gaat allemaal prima want als ik ze met een itterator op het scherm zet klopt dit allemaal

wat ik nu wil is in deze linkedlist gaan zoeken ofterwijl ik wil een nieuwe linkedlist hebben waar alle filenames in staan waarin een vooraf ingestelde string in voorkomt

heeft iemand een id hoe ik dit kan doen want zovel als ik weet kun je in een linkedlist niet zoeken...

[narotic]

Tuurlijk kan je wel zoeken in een linked list. Het principe is gewoon om met de iterator langs alle nodes te gaan en te kijken of die voldoen aan je zoekopdracht.

Als dat zo is, dan creeer je gewoon een nieuwe linkedlist met alle nodes die voldoen.

[Verwijderd]

narotic schreef op 26 februari 2004 @ 19:35:
Tuurlijk kan je wel zoeken in een linked list. Het principe is gewoon om met de iterator langs alle nodes te gaan en te kijken of die voldoen aan je zoekopdracht.

Als dat zo is, dan creeer je gewoon een nieuwe linkedlist met alle nodes die voldoen.

ja dat is inderdaad een optie maar op een andere manier die er standaard is gaat dit dus niet begrijp ik... want elke keer n itterator doorlopen kost elke keer weer wat tijd...

[Macros]

LinkedList is ook niet snel om te doorzoeken. Het ligt er een beetje aan naar wat je wilt zoeken. Ligt er een beetje aan naar wat je wilt zoeken over wat voor datastructuur je het beste kan nemen.

[narotic]

Wat voor standaard optie had je verwacht dan?

Stel dat er een methode LinkedList.Search() in de API zou staan, dan nog zou deze op precies dezelfde manier zoeken. Zo zit deze datastructuur nu eenmaal in elkaar...

[Robtimus]

Idd, elke vorm van zoeken in een lijst kan alleen maar met een lineair search, tenzij er genoeg structuur is voor een binairy search. Dat is hier niet het geval.

Ik hoop dat je gebruikt maakt van File.listFiles(FileFilter) voor het zoeken?

[ACM]

De Collections-interface definieert een retainAll methode, wellicht dat je daar wat aan hebt. Eventueel kan je je te doorzoeken lijst eerst nog in een ArrayList ofzo stoppen of eventueel niet met Lists werken, maar er een HashSet van maken, die is waarschijnlijk lekker snel te gebruiken met retainAll.

Zie voor meer informatie over collections: http://java.sun.com/j2se/...de/collections/index.html

[Verwijderd]

als je de linkedlist hebt, kun je toArray() gebruiken, dan via Arrays.asList er een List van maken en daar een ArrayList mee construeren.

En eigenlijk lijkt het me beter omgekeerd te werken. Je maakt de arraylist met alle files, filtert, en bouwt daar dan op genoemde wijze een linkedlist mee....

Tuurlijk is de vorige optie met een FileFilter ook geschikt, tenzij je meerdere keren wil filteren (en je dus niet telkens opnieuw die List wil opbouwen. Je kan dan een clone uitvoeren ofzo)

[ACM]

is het niet sneller/handiger om gewoon je linkedlist in de constructor van je arraylist te stoppen, voodoochile?

[BestTested!]

Of gewoon meteen al die bestandsnamen in een ArrayList gooien. Als je ze in een sortbaar Data Type gooit, en dan met binary search zoekt, is dat niet sneller? Desnoods gooi je zelf een abstract data type inelkaar. Ik weet niet hoeveel het een langzamer/sneller is, heb ff geen tijd om de tijdcomplexiteit uit te rekenen.

[Janoz]

BestTested! schreef op 27 februari 2004 @ 09:48:
Of gewoon meteen al die bestandsnamen in een ArrayList gooien. Als je ze in een sortbaar Data Type gooit, en dan met binary search zoekt, is dat niet sneller? Desnoods gooi je zelf een abstract data type inelkaar. Ik weet niet hoeveel het een langzamer/sneller is, heb ff geen tijd om de tijdcomplexiteit uit te rekenen.

Als je zoekt op delen van de bestandsnaam haal je geen voordeel uit het gesorteerd opslaan van de data (er zijn echter een heleboel andere bewerkingen waarbij het gesorteerd hebben van gegevens weer wel handig is )

[BestTested!]

Verwijderd schreef op 26 februari 2004 @ 19:33:
....naar bestanden met een opgegeven extensie. ...

Sorteren op extensie dus.

[Macros]

Ik zou per verschillende extensie een ArrayList maken, en die ArrayLists in een HashMap doen met als key de extensie. Wil je over alle bestanden iteraten, dan iterate je over de HashMaps en voor elke HashMap over de ArrayList en zoek je alleen bestanden met een bepaalde extensie, dan haal je die zo op uit de HashMap.

[ Voor 3% gewijzigd door Macros op 27-02-2004 10:39 ]

[Robtimus]

Vraagje: moet je die lijst met ALLE bestanden met die extensie hebben? Zo niet, dan kun je al in je originele FileFilter filteren:

Java:

import java.io.*;
import java.util.*;

public class Filter implements FileFilter
{
    private String ext;
    private String searchStr;
    private boolean caseSensitive;

    public Filter(String ext, String searchStr, boolean caseSensitive)
    {
        this.ext = ext;
        this.searchStr = searchStr;
        this.caseSensitive = caseSensitive;
    }

    public boolean accept(File file)
    {
        if (file.isDirectory())
        {
            return true;
        }
        String name = file.getName();
        if (!name.endsWith("." + ext))
        {
            return false;
        }
        if (caseSensitive)
        {
            return name.indexOf(searchStr) != -1;
        }
        else
        {
            return name.toLowerCase().indexOf(searchStr.toLowerCase()) != -1;
        }
    }

    public static List getFiles(File start, FileFilter filter)
    {
        List list = new ArrayList();
        File[] files = start.listFiles(filter);
        for (int i = 0; i < files.length; i++)
        {
            if (files[i].isFile())
            {
                list.add(files[i].getAbsolutePath());
            }
            else if (files[i].isDirectory())
            {
                list.addAll(getFiles(files[i], filter));
            }
        }
        return list;
    }

    public static void main(String[] args) throws IOException
    {
        File startDir = new File(args[0]);
        String ext = args[1];
        String searchStr = args[2];
        boolean caseSensitive = Boolean.valueOf(args[3]).booleanValue();
        Filter filter = new Filter(ext, searchStr, caseSensitive);
        List l = getFiles(startDir, filter);
        for (Iterator i = l.iterator(); i.hasNext(); )
        {
            System.out.println(i.next());
        }
    }
}

[Robtimus]

Macros schreef op 27 februari 2004 @ 10:39:
Ik zou per verschillende extensie een ArrayList maken, en die ArrayLists in een HashMap doen met als key de extensie. Wil je over alle bestanden iteraten, dan iterate je over de HashMaps en voor elke HashMap over de ArrayList en zoek je alleen bestanden met een bepaalde extensie, dan haal je die zo op uit de HashMap.

Dit is ontzettend geheugen inefficient, zeker als je maar 1 extensie nodig hebt. Dan kun je beter een FileFilter gebruiken.
Heb je meerdere extensies nodig, dan is dat een tradeoff tussen processorgebruik (meerdere keren met een FileFilter werken) of geheugengebruik (1x alles opslaan).

[Macros]

IceManX schreef op 27 februari 2004 @ 10:47:
[...]
Dit is ontzettend geheugen inefficient, zeker als je maar 1 extensie nodig hebt. Dan kun je beter een FileFilter gebruiken.
Heb je meerdere extensies nodig, dan is dat een tradeoff tussen processorgebruik (meerdere keren met een FileFilter werken) of geheugengebruik (1x alles opslaan).

Ligt eraan hoeveel bestanden je er in zet. In plaats van een ArrayList kan je ook een LinkedList gebruiken, maar die kan je weer niet sorteren.
Stel je wilt een soort medialibrary maken. Dan ipv de extensie als key te nemen, neem je de mediasoort, film, muziek, plaatje, whatever. En dan kan je die individuele Lists sorteren op naam. Je FileFilter houdt alle bestanden uit je data structuur waar je niet op wilt zoeken. Ik bedoelde niet dat je gewoon alle bestanden er in moest zetten, alleen degene waar je geinterseerd ben.

[Verwijderd]

ACM schreef op 26 februari 2004 @ 22:49:
is het niet sneller/handiger om gewoon je linkedlist in de constructor van je arraylist te stoppen, voodoochile?

bloos