[IN] Is het mogelijk om twee lijsten in O(n) tijd met elkaar te vergelijken?

[Rob]

Ik zit met een vraagje (meer uit interesse dan omdat het moet. :p).

Ik heb twee identieke, geïndexeerde lijsten (tabellen, liever gezegd, maar dat terzijde). Zie hier:

+-------+-------------+--------------------------+   +-------+-------------+--------------------------+

| index |   Document  |          Patroon         |   | index |   Document  |          Patroon         |

+-------+-------------+--------------------------+   +-------+-------------+--------------------------+

|   0   | intro_info  | [1, 2, 3, 1, 2, 2, 2, 3] |   |   0   | intro_info  | [1, 2, 3, 1, 2, 2, 2, 3] |

+-------+-------------+--------------------------+   +-------+-------------+--------------------------+

|   1   | richtlijnen |         [1, 2, 3]        |   |   1   | richtlijnen |         [1, 2, 3]        |

+-------+-------------+--------------------------+   +-------+-------------+--------------------------+

|   2   | contract v3 |   [1, 2, 2, 2, 2, 2, 3]  |   |   2   | contract v3 |   [1, 2, 2, 2, 2, 2, 3]  |

+-------+-------------+--------------------------+   +-------+-------------+--------------------------+

Links lijst 1, rechts lijst 2. Deze kunnen net zo lang worden als nodig en beginnen te tellen bij 0.

Wanneer de indices gelijk zijn, willen we niet vergelijken, anders wel. We hebben 'm al subkwadratisch door ervoor te zorgen dat wanneer beide indices gelijk zijn, de inner loop niet uitgevoerd wordt, maar ik was dus benieuwd of een O(n) (of in ieder geval sneller dan een subkwadratisch) algoritme ook mogelijk is, aangezien deze lijsten akelig lang kunnen gaan worden.

0,1 (rij 0 in lijst 1, rij 1 in lijst 2) is equivalent aan 1,0, in dit geval. Is het mogelijk om een algoritme te ontwerpen dat alle (x,x) coördinaten overslaat èn dat de inverses van al gedane verglijkingen ook overslaat? Ik heb er wel naar zitten kijken, maar kwam per ongeluk op een zigzag-algoritme dat niet echt werkt. :D

Of is het misschien sneller en makkelijker om die dingen er zelf uit te werken en dan te vergelijken?

[ILUsion]

Of het in O(n ) uit te werken is, ik vrees ervoor. Wat je zou kunnen proberen om te zien of het sneller gaat: gewoon overal van elk van die elementen in je lijsten een hash berekenen indien mogelijk en die vergelijken (dan loop je elk van die lijsten maar 1 keer door in het begin) en hashes vergelijken gaat normaal wel vrij snel. Het nadeel is wel dat je dan voor elke bijkomende tabel meer geheugen gaat gebruiken.

Gedane vergelijkingen overslaan, is meestal doenbaar door maar over 1 lijst te itereren en die te vergelijken met 0 tot en met de huidige index in de geïtereerde lijst; alleen lukt dat op het eerste gezicht niet zo bij wat je wilt. Ik begrijp ook al amper het nut van wat je aan het doen bent (dus is het best moeilijk te visualiseren).

[IvdSangen]

Ik heb niet alles begrepen van je post, maar de volgende vraag kan ik beantwoorden:

Is het mogelijk om een algoritme te ontwerpen dat alle (x,x) coördinaten overslaat èn dat de inverses van al gedane verglijkingen ook overslaat?

Het antwoord is "ja, dat kan". En wel op de volgende manier:

for (int i = 0; i < n; i++) {
        for (int j = i+1; j < m; j++ {
                compare(i,j);
        }
}

Edit: Dit is nog steeds een kwadratisch algoritme overigens. Beter gezegd O(n*m).