SortedList vs Hashmap: unions en intersections

[MrBucket]

Stel dat je set-operaties als union en intersection zo efficient mogelijk wilt uitvoeren, welke datastructuur zou je dan moeten gebruiken? Een gesorteerde lijst (in de vorm van een gebalanceerde binaire boom of skiplist), of een op hashing gebaseerde datastructuur (meestal Hashtable of hashmap genoemd)?

Ik kan hier zelf geen eenduidig antwoord op bedenken. Ik weet dat een element opzoeken in een hashtable een O(1) operatie is, terwijl dit voor een gesorteerde lijst O(log n) is. Echter, een union of intersection tussen twee gesorteerde lijsten kan in O(n) geimplementeerd worden.

Voor een hashmap zou je n keer een O(1) lookup moeten doen, dus dat zou ook O(n) zijn, lijkt me.

Welke van de twee datastructuren zou het best performen?

[KopjeThee]

Als je een boom structuur tegen hash overweegt, dan zou ik hash kiezen. Als je een echte gelinkte lijst tegen hash overweegt, zal het niet veel uitmaken, denk ik. Waarschijnlijk dan de gelinkte lijst, omdat de performance daarvan gegarandeerd is, terwijl hashfunctie misschien wat collisions kunnen hebben.

[DroogKloot]

Een intersectie van twee sets uitvoeren vereist voor elk element in de tweede set controleren of het in de eerste voorkomt (zoja, dan behoort het tot de intersectie). Dat is dus minimaal een O(n log n) operatie wanneer beide sets gebalanceerde binaire bomen zijn en je de eerste set onaangetast laat: de tweede set bevat n elementen waarvoor de lookup-/insertie-tijd elk O(log n) is. Een vereniging kost evenveel tijd om dezelfde reden, die bestaat namelijk uit alle elementen in set 1 plus die elementen uit set 2 welke niet al in 1 voorkwamen.

Gebruik je een hashtable dan is de *verwachtte* lookup-tijd van een element inderdaad O(1), maar afhankelijk van de load factor en de manier waarop de table met collisions omgaat (separate chaining danwel open addressing plus een vorm van probing) is dat nooit echt gegarandeerd. Bovendien is er de complicatie dat de table om de zoveel inserties opnieuw opgebouwd moet worden, maar dat vergt (geamortiseerd) constante tijd. Als datastructuur voor een set is een hashtable dus wel efficienter, lijkt me.

[ Voor 3% gewijzigd door DroogKloot op 10-02-2007 23:26 ]

[MrBucket]

DroogKloot schreef op zaterdag 10 februari 2007 @ 23:13:
Een intersectie van twee sets uitvoeren vereist voor elk element in de tweede set controleren of het in de eerste voorkomt (zoja, dan behoort het tot de intersectie). Dat is dus minimaal een O(n log n) operatie wanneer beide sets gebalanceerde binaire bomen zijn en je de eerste set onaangetast laat: de tweede set bevat n elementen waarvoor de lookup-/insertie-tijd elk O(log n) is. Een vereniging kost evenveel tijd om dezelfde reden, die bestaat namelijk uit alle elementen in set 1 plus die elementen uit set 2 welke niet al in 1 voorkwamen.

Dat hoeft niet. Van twee gesorteerde lijsten kun je in lineaire tijd de union of intersection vinden (zie bijv. http://www2.toki.or.id/bo...al/BOOK/BOOK3/NODE133.HTM:
However, it is usually useful for implementation to represent each set in a single canonical order, typically sorted, so as to speed up or simplify various operations. Sorted order turns the problem of finding the union or intersection of two subsets into a linear-time operation - just sweep from left to right and see what you are missing.

Het enige wat hierop af te dingen is, is wanneer er geen volledige ordening is gedefinieerd op de elementen, d.w.z.: wanneer er voor 1 of meer subsets {e₁...e_k} geldt dat (e_m < e_n) = false en (e_m > e_n) = false, terwijl e_m != e_n. In dat geval zul je voor deze subsets alsnog op een O(n²) manier deze elementen met elkaar moeten vergelijken, omdat de ordening je hiermee niet kan helpen.

Zou een hashtable nu nog steeds efficienter zijn?

[EfBe]

wanneer er voor 1 of meer subsets {e1...ek} geldt dat (em < en) = false en (em > en) = false, terwijl em != en.

Dat kan niet. Ik denk dat je OF bedoelt

Overigens is een hashmap niet O(1), alleen bij de ultieme hashfunctie die nooit dupes oplevert. In de praktijk heb je altijd duplicates in je buckets die je dus in lineare tijd moet doorzoeken.

[MrBucket]

EfBe schreef op zondag 11 februari 2007 @ 17:11:
[...]

Dat kan niet. Ik denk dat je OF bedoelt

Nee, ik bedoelde echt 'en', maar de vraag of de door mij beschreven situatie voor mag komen of niet is inderdaad wel een twijfelgeval.
Stel dat je bijvoorbeeld een lijst van Persoon objecten hebt, en de gedefinieerde ordening op deze objecten is dat ze alleen op hun geboortedatum worden gesorteerd. Op het moment dat je twee personen in die lijst hebt staan die op dezelfde dag geboren zijn, heb je de situatie dat geen van beide personen als 'kleiner' of 'groter' kan worden beschouwd als de ander, terwijl het wel verschillende personen zijn. Tussen deze twee personen is dus gewoon geen ordening gedefinieerd.

Dit is natuurlijk op te lossen door lexicografisch op alle eigenschappen van een Persoon te ordenen zodat er altijd een ordening bestaat, maar het lijkt me dat je ook met niet-complete ordeningen wil kunnen werken.

Overigens is een hashmap niet O(1), alleen bij de ultieme hashfunctie die nooit dupes oplevert. In de praktijk heb je altijd duplicates in je buckets die je dus in lineare tijd moet doorzoeken.

Maar als je een enigszins degelijke hashfunctie hebt, heb je altijd maar een klein aantal elementen per bucket, zodat het zoeken in zo'n bucket nagenoeg O(1) is.

[EfBe]

MrBucket schreef op zondag 11 februari 2007 @ 18:05:
[...]

Nee, ik bedoelde echt 'en', maar de vraag of de door mij beschreven situatie voor mag komen of niet is inderdaad wel een twijfelgeval.
Stel dat je bijvoorbeeld een lijst van Persoon objecten hebt, en de gedefinieerde ordening op deze objecten is dat ze alleen op hun geboortedatum worden gesorteerd. Op het moment dat je twee personen in die lijst hebt staan die op dezelfde dag geboren zijn, heb je de situatie dat geen van beide personen als 'kleiner' of 'groter' kan worden beschouwd als de ander, terwijl het wel verschillende personen zijn. Tussen deze twee personen is dus gewoon geen ordening gedefinieerd.

Ah, ok daar had ik even niet aan gedacht. Goed punt

[Verwijderd]

MrBucket schreef op zondag 11 februari 2007 @ 18:05:
[...]

Dit is natuurlijk op te lossen door lexicografisch op alle eigenschappen van een Persoon te ordenen zodat er altijd een ordening bestaat, maar het lijkt me dat je ook met niet-complete ordeningen wil kunnen werken.

Sterker nog, ook lexicografisch ordenen werkt niet altijd. Het is immers niet onmogelijk om twee personen met dezelfde naam, geboortedatum, geslacht, etc. te hebben, die toch niet dezelfde persoon zijn....