Zwei listen vergleichen?

Heyho, ich hätte da eine frage, unswar möchte ich zwei riesige listen vergleichen. Also ich habe zwei listen mit so vielen begriffen, dass es mir unmöglich erscheint sie alle durchzusehen. Mein ziel ist es aber, aus beiden listen jeden gemeinsamen begriff herauszufiltern.Also:

liste 1. Liste 2.

Tisch. Stuhl

tomate. Orange

banane. Tisch

jz sieht man das tisch in beiden listen vorhanden ist und dann möchte ich dass dieses wort angezeigt wird und dass für riesige listen. Kann mir da vielleicht jemand helfen?

5 Antworten

milos2

27.04.2019, 19:37

Sortiere die zweite Liste mit dem Mergesort
Iteriere über die erste Liste
Suche den aktuellen Eintrag der ersten Liste in der zweiten Liste über eine binäre Suche (diese setzt die obige Sortierung voraus)

Woher ich das weiß:Studium / Ausbildung

milos2

27.04.2019, 19:46

Ich hoffe du arbeitest nicht mit Arrays sondern verketteten Listen.

safur

Nutzer, der sehr aktiv auf gutefrage ist

im Thema Informatik

27.04.2019, 19:34

Hast du Excel oder SQL?

Excel:

Tabellenblatt "Übersicht"

Du kopierst dir beide Listen untereinander und entfernst die doppelten Einträge.
--> Vereinigungsmenge

Nun erstellst du ein Tabellenblatt "Liste1" und füllst Liste 1 ein
Nun erstellst du ein Tabellenblatt "Liste2" und füllst Liste 2 ein

Bei deinem Übersichtsblatt machst du nun einen SVERWEIS des Begriffst auf Liste1 und daneben auf Liste 2

Fertig 😃

milos2

27.04.2019, 19:48

Nein, Excel wäre doch mit ein paar Millionen einträgen Überfordert. Für solche Zwecke nutzt man vernünftige Lösungen. Ich würde es in Java lösen.

safur

27.04.2019, 19:51

@milos2

Er hat nicht von Millionen gesprochen 😉

Gurkenbruder

27.04.2019, 20:22

Der naivste Ansatz hätte vermutlich O(n*m) worstcase (alle Elemente nacheinander vergleichen).

Zusammen mit dem Aufbau der Liste ist das O(n*m+n+m)

Ich gehe jetzt davon aus, dass der Aufbau der Liste und das Suchen in einem 1:1 Verhältnis stehen (d.h. für zwei beliebige Listen werden genau 1x die doppelten Werte benötigt)

Dann ist die Frage, von wo bekommst du die Liste?

Das möglichst effiziente wäre nämlich schon beim Aufbau der beiden Listen stattdessen eine Datenstruktur zu verwenden wo man in konstanter oder linearer Zeit doppelte Einträge rausfiltern kann.

z.B. eine Wrapperklasse mit einer Hashmap wo du beim Einfügen jedes Elementes der Listen 1 und 2 folgendes tust:

Prüfe ob Key mit dem zu speichernden Element in Hashmap bereits vorhanden (konstante Zeit mit containsKey)
Wenn nein -> Füge (Wert, 1) hinzu (konstante Zeit da put O(1); wenn ja -> Erhöhe x in (Wert, x) um 1 (konstante Zeit da get O(1))
Nun kannst du über eine Methode getDuplicate() einfach alle HashMap Keys mit Value > 1 zurückgeben (O(n+m))

Damit hast du insgesamt für den Aufbau der Liste + das Finden der doppelten Elemente eine worst case Laufzeit von O(2(n+m)).

Hier musst du aber beachten, dass Liste 1 und Liste 2 selber keine doppelten Einträge beinhalten dürfen.

Woher ich das weiß:Studium / Ausbildung – Promoviert

Einstein0815

27.04.2019, 19:48

Die Listen zu sortieren wäre nicht gut, da dies einen O(n log n)-Aufwand erfordern würde. Stattdessen hier die O(n)-Lösung: Speichere alle Worte aus Liste 1 in eine Hashtabelle und suche in dieser die Worte aus der Liste 2. Fertig!

Woher ich das weiß:Studium / Ausbildung

gwf79

27.04.2019, 19:59

Muß man die Hashwerte dann nicht trotzdem sortieren, um effizient in ihnen suchen zu können?

Einstein0815

27.04.2019, 20:04

@gwf79

Nein, der Witz bei einer Hashtabelle ist ja, dass sie aus unsortierten Daten erstellt werden kann und unsortiert im Speicher herumliegt, trotzdem aber jedes Datum mit O(1) Aufwand gefunden werden kann.

buffalo23

27.04.2019, 19:34

In welcher Form liegen die Daten vor?

Ähnliche Fragen

C#: Vergleichen von zwei Objekten?

Hallo,

ich habe zwei Listen mit Objekten.

Was ist der beste Weg, um die Objekte der Listen zu vergleichen?

Beispiel-Klasse:

class Person
{
  int Id;
  string Name;
  String Adresse;
  IEnumerable<string> Telefon
}

In jeder Liste sind 150 Einträge vorhanden.

Wie kann ich nun herausfinden, ob sich Werte der Liste verändert haben, indem ich die Objekte vergleiche?

...zur Frage

Welche Lebensmittel dürfen in Kompost?

Ich wollte mal wissen,welche Lebensmittel man in Kompost werfen darf. Bitte nur Antworten in so einer Art Liste,wie z.B. Äpfel,Bananen,Wurst,Brot,Tomaten,... Danke

...zur Frage

Pc vergleich welcher ist besser?

Hey Leute ich und mein Bruder haben 3 verschiedene PC konfiguriert und wir wollten jetzt wissen welcher der beiden Besser ist. Mit Begründung bitte.

https://de.pcpartpicker.com/list/9R7mQP
https://de.pcpartpicker.com/list/pPwVbL
https://www.alternate.de/configurator.xhtml?cshsv=405d3477-3ee2-471d-9b21-dbd0921f9132

Danke schon mal im Voraus.

Hoffe auf schnelle Antwort

...zur Frage

Java Listen-Elemente an Stelle x bis unendlich ausgeben?

Hallo möchte in Java von einer Liste alle Element ab der Stelle x ausgeben. das heißt bei der Liste ["Apfel", "Zitrone", "Birne", "Banane"] soll zum Beispiel alles ab "Zitrone" (Index 1) ausgegeben werden -> "Zitrone", "Birne", Banane". Als Vergleich: In Python kann man liste[1:] verwenden. Gibt es sowas auch in Java?

...zur Frage

Python - Itertools Liste vergleichen?

Hallo,

ich habe aus einer Textdatei jede einzelne Zeile mit Hilfe von Itertools

a = combinations(zeilen, 2)

alle Möglichen Kombinationen in Zweiergruppen gepackt. Diese möchte ich nun mit Hilfe von fuzzywuzzy untereinander vergleichen. Das Problem ist, bei der Art vergleich werden zwei Angaben benötigt.

ratio = fuzz.ratio(zeile1, zeile2)

Meine Gruppe a habe ich aber ja nur einmal? Also klappt das folgende nicht

ratio = fuzz.ratio(a)

Wie genau kann ich dieses Problem lösen?

...zur Frage

Ich esse täglich einen apfel, eine banane, drei orangen, 100 gramm beeren und im sommer auch noch anderes obst und eine karotte, einen spitzpaprika, 3 tomaten?

Und auch anderes gemüse. Ist das ok und gesund? Also zwei hände voll obst und zwei.voll gemüse!

...zur Frage

Python: Listen vergleichen?

Hi,

ich würde gerne in einer Schleife, zwei Listen, welche beide Elemente mit Wörtern enthalten, miteinander vergleichen. Von einer Liste möchte ich das Anfangswort in der anderen Liste suchen, um einen möglichen Treffer daraufhin weiter zu untersuchen.

for i in range(länge_ganzer_text):
  if nur_woerter[0] in alle_woerter[i]:

Ich habe das versucht, aber es gibt die Fehlermeldung:

list index out of range

...zur Frage

Wie kann man doppelte Werte in Python anzeigen lassen?

Hey! Ich würde gerne in Python folgendes machen:

Gegeben sind zwei Listen mit beliebiger Anzahl an Strings:

list_1 = ["Gute", "Frage", "Python"]
list_2 = ["Gute", "Antwort"]

Nun sollte das Programm herausfinden, welche dieser Werte in beiden Liste vorkommen und diese dann auf der Console anzeigen:

if list_1.__contains__("Gute") and list_2.__contains__("Gute"):
    print("Gute")

Das Problem: Aufgrund meiner noch geringen Kentnisse, weiss ich nicht, wie ich diesen Teil verallgemeinern kann. Ich kann zwar mit .contains herausfinden, ob sich spezifische Stings in den Listen befinden und kann dann somit eine Aktion ausführen, jedoch ist dies schwachsinnig, wenn ich mehrere if-Befehle machen müsste. Zudem wird der Befehl nur ein einziges Mal ausgeführt, wenn die Voraussetzungen wahr sind.

Wie kann ich den Code so umschreiben, dass es nach zwei deckungsgleichen Stings sucht und den Namen, der jeweils doppelten Strings auf der Console anzeigt, ohne dass ich irgendwelche Plug-ins importieren muss? Am besten wäre eine while Schleife geeignet, da if nur ein einziges Mal ausgeführt wird. Ich arbeite mit Replit & PyCharm.

...zur Frage

Realos und Fundis?

Hallo, diese Frage richtet sich an die Leute die sich mit Bündnis 90/ Die Grünen auskennen. Und zwar geht geht es um die beiden Begriffe Realos und Fundis... Ich habe mitbekommen, dass es da zwei "Aufspaltungen" gibt aber wie weit unterscheiden sich die Politischen Richtungen der beiden Begriffe miteinander? Oder hab ich das völlig falsch verstanden...

Ich würde mich riesig auf eine Antwort freuen... Lg

...zur Frage

Python verschiedene Objekte, gleiche Referenz?

Ich habe eine Liste erstellt und habe zwei verschiedene Objekte erzeugt, mit verschiedenen Attributen, und diese der Liste hinzugefügt. Als ich dann den Wert eines Attributs ändern wollte, hat sich auch das Attribut des anderen Objekts geändert.

Hiernach habe ich die Objekt Referenzen kontrolliert, und da ist mir aufgefallen, dass beide Objekte die gleiche Referenz haben. Aber wie kann das sein, wenn die beiden verschiedene Attributwerte haben, und wie kann ich es beheben, dass die beiden Objekte nicht die selbe Referenz haben?

Pastebin Link: https://pastebin.com/55avRgd0

...zur Frage

Wie kann man bei Python zwei Elemente einer Liste vergleichen?

Ich möchte vergleichen ob der vorherige Wert einer Liste kleiner ist als der aktuelle bei 1000 Werten. Kann man das irgendwie in eine Schleife schreiben?

...zur Frage

Informatik Java Rechtecke vergleichen?

Ein achsenparalleles Rechteck ist durch die Koordinaten von zwei gegenüberliegenden Eckpunkten P(px, py) und Q(qx, qy) bestimmt. Schreiben Sie ein Java Programm Rectangles, das die Lage zweier gegebener achsenparalleler Rechtecke zueinander in einem Koordinatensystem bestimmt und folgende Fälle unterscheidet:

disjoint

Die Schnittmenge der beiden Rechtecke ist leer, sie haben keinen gemeinsamen Punkt. same Die Lage und Größe beider Rechtecke sind gleich.

contained

Der Durchschnitt der beiden Rechtecke entspricht genau einem der beiden Rechtecke. Alle Punkte des einen Rechtecks sind auch in dem anderen enthalten, aber nicht umgekehrt.

aligned

Der Durchschnitt der beiden Rechtecke ergibt eine Linie. Alle gemeinsamen Punkte liegen auf einer Linie mit einer Länge > 0.

touching

Der Durchschnitt der beiden Rechtecke ergibt einen Punkt. Beide Rechtecke haben genau einen gemeinsamen Punkt.

intersecting

Der Durchschnitt der beiden Rechtecke ergibt ein weiteres Rechteck mit einem Flächeninhalt > 0. Ihr Programm liest acht Argumente von der Kommandozeile ein.

Dies sind die beiden Koordinaten P(px, py) und Q(qx, qy) des ersten Rechtecks sowie die Koordinaten S(sx, sy) und T(tx, ty) des zweiten Rechtecks. Berechnen Sie die Lage der beiden gegebenen Rechtecke zueinander und geben Sie das zugehörige Schlüsselwort entsprechend obiger Liste aus.

Beispiel: Für die beiden Rechtecke P(2, 2), Q(7, 5) und S(3, 4), T(0, 6) liefert der Aufruf

C:\> java Rectangles 2 2 7 5 3 4 0 6

intersecting

Ich möchte es mit if befehl machen habe aber keinen plan wie ich die miteinander vergleichen soll :D

...zur Frage

Habe zwei int Variablen die mehrere Werte haben, ich soll beide Variablen vergleichen und wenn die gleiche Werte haben nur die gleichen Wert ausgeben wie (java?

Hi, ich habe zwei int Variablen mit sehr vielen Zahlen, diese soll ich vergleichen miteinander. Wenn die zwe int Variablen irgendwo gleiche Zahlen haben soll ich nur diese Zahl ausgeben.

Wie mache ich das?

...zur Frage

Geografie?

Hallo, ich mache gerade so Übungen für die Geografie Prüfung unswar mit Atlas. :)
Könnt ihr mir bitte helfen:

Die Aufgaben:

Ermitteln Sie mithilfe des Atlas für die beiden Wirtschaftsregionen Kalifornien und Golfküstenregion jeweils vier dominierende Industriezweige, zwei wichtige Industriestädte sowie bedeutende Rohstoffvorkommen.
Vergleichen Sie die beiden Wirtschaftsregionen Kalifornien und Golfküstenregion.
Begründen Sie die nachfolgende Aussage: „Die vielfältigen Standortvorteile haben den Aufstieg der USA zur Weltwirtschaftsmacht begünstigt."

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen