[Java] Zoeken in een byte array

[pjonk]

Hoi,

Ik wil een byte array gaan manipuleren.
Een bepaalde reeks bytes moet uit het byte array worden gefilterd.

Ik hoorde dat er tegenwoordig ook een ByteBuffer class beschikbaar is, maar ik begreep dat die alleen in de nieuwste JDK aanwezig was. Helaas is dat voor mij dan geen optie ivm de Server.

Het enige wat ik hoef te doen is zoeken naar een bepaalde reeks bytes in het byte array.
Maar het lijkt mij nogal traag om met een For i lusje byte voor byte het array af te lopen.
Is er buiten de ByteBuffer een andere manier om te zoeken in een Byte array? Ik kon helaas niks in mijn Java boek vinden.

[Glimi]

Waarom stop je het niet in een linked list dan, en ga je een binairy search erop loslaten

[edit]Inderdaad ik moet wel leren lezen Een reeks bytes is al een stukje anders
excuus domme opmerking hierboven

[edit2] wrijf het er nog even in joh .oisyn Ik had inderdaad verkeerd gelezen. Ik dacht dat hij wou weten of een bepaalde byte in z'n collectie zat, en dan kan een Binairy tree (speciale linked list idd) van pas komen als de volgorde niet uitmaakt.
Heb ik het zo weer een beetje goed gemaakt

[Verwijderd]

[wijsneus mode]

Bytes in een linked list stoppen lijkt me niet echt de meest efficiente oplossing.

[/wijsneus mode]

Jammergenoeg weet ik ook niks beter Maar zoeken door een array is over het algemeen toch best efficient, waarom probeer je het niet eerst zo?

[edit]
typos

[pjonk]

Inderdaad ik moet zeggen dat de performance goed is.
Ik loop nu gewoon met een for i lusje elke byte af en filter bepaalde bytes.
Ik dacht even dat een byte array doorlopen niet zo efficient zou zijn.

[Soultaker]

Ken je klassieke algoritmen.

Een ongeordende reeks is te doorzoeken met complexiteit O(M + N) (met M en N de lengte van de reeks respectievelijk de te vinden reeks). Eventueel kun je een suffix-tree bouwen om vervolgens met complexiteit O(N) te kunnen zoeken, maar dat is nogal complex en meestal overkill.

Bedenk dat het vinden van een element in een array in constante tijd (en ook nog eens heel snel) gaat, in een imperatieve programmeertaal. Een lusje is dus erg efficiënt.

[.oisyn]

Op donderdag 20 juni 2002 12:27 schreef Glimi het volgende:
Waarom stop je het niet in een linked list dan, en ga je een binairy search erop loslaten

binary search gaat moeilijk met een linked list, daar heb je een binaire boom voor nodig

Het gaat echter ook met een gesorteerde array: het middelste element is je root, en daar wordt de array ook opgedeeld in sub-arrays. Het middelste element van de linker sub-array is de linker child van de root en het middelste element van de rechter sub-array is de rechter child van de root. Die kun je ook weer onderverdelen en ga zo maar door.

Dit is echter geen oplossing voor de topicstarter zoals je zelf al aangaf

Op donderdag 20 juni 2002 16:42 schreef Soultaker het volgende:
Ken je klassieke algoritmen.

Een ongeordende reeks is te doorzoeken met complexiteit O(M + N) (met M en N de lengte van de reeks respectievelijk de te vinden reeks). Eventueel kun je een suffix-tree bouwen om vervolgens met complexiteit O(N) te kunnen zoeken, maar dat is nogal complex en meestal overkill.

hmm is dat dat algoritme waarbij je de grote reeks doorloopt door steeds te kijken naar de achterste byte? Komt deze byte in de te vinden reeks voor dan moet je een aantal plaatsen terug (waarvoor je een tabelletje hebt gemaakt waarin voor elke letter staat hoeveel plaatsen je terug moet), en anders kun je M plaatsen verder (immers, het huidige teken komt niet in de te vinden reeks voor, dus de reeks zou kunnen beginnen op de plaats van het volgende teken. Maar omdat je steeds de achterste controleert ipv de voorste moet je dus nog eens M - 1 plaatsen vooruit bewegen, in totaal dus M)

Zo ja, weet je toevallig wat de naam is van dit algoritme? Ik vergeet m steeds En zo nee, weet je dan toevallig toch nog wat de naam is van dit algoritme?

[Soultaker]

Op donderdag 20 juni 2002 17:39 schreef .oisyn het volgende:
hmm is dat dat algoritme waarbij je de grote reeks doorloopt door steeds te kijken naar de achterste byte? Komt deze byte in de te vinden reeks voor dan moet je een aantal plaatsen terug (waarvoor je een tabelletje hebt gemaakt waarin voor elke letter staat hoeveel plaatsen je terug moet), en anders kun je M plaatsen verder (immers, het huidige teken komt niet in de te vinden reeks voor, dus de reeks zou kunnen beginnen op de plaats van het volgende teken. Maar omdat je steeds de achterste controleert ipv de voorste moet je dus nog eens M - 1 plaatsen vooruit bewegen, in totaal dus M)

Ik zou het niet kunnen bevestigen, aangezien ik het algoritme nooit heb geprobeert te implementeren (er was nooit noodzaak toe) en ik het dus niet precies uit m'n hoofd ken.

De bedoeling is een suffix-boom te bouwen (een boom met daarin alle suffices van je string en de positie waarop ze beginnen) en het lineaire algoritme daarvoor staat bekend als het algoritme van Ukkonen. Of dat 't algoritme is dat jij bedoelde, weet ik helaas niet zeker.