Re: Doppelte Einträge in Array so schnell wie möglich finden



Hallo,

Mein Ziel ist es dabei so schnell wie möglich zu sein, daher wandle
ich die Arrays bisher in Dictionarys um und mache es damit, doch
selbst das ist mir noch zu langsam.

Die Umwandlung ist selber ja schon zeitraubend.
Um die beste Methode zu finden, käme hier auch
darauf an, ob sortiert, welche Verteilung und Längen
die einzelnen Arrays haben. Also kaum in einem
Satz formulierbar.

Man fragt sich, ob Dir denn LINQ ausreicht?

int[] arr1 = new int[] { 1, 3, 4, 6, 9, 10 };
int[] arr2 = new int[] { 2, 3, 5, 9 };
var doppelte = arr1.Intersect(arr2);

Die Implementation geht hier intern über
Hash Algorithmen und recht effizient.


____________
Ansonsten auch:

[Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences]
http://www.cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf

[Algorithm to find if two sets intersect - Stack Overflow]
http://stackoverflow.com/questions/245557/algorithm-to-find-if-two-sets-intersect



Ich habe viel darüber gelesen, dass die schnellste Methode für so
etwas mit BitArrays wäre, ...

welche zum Beispiel?


ciao Frank
--
Dipl.Inf. Frank Dzaebel [MCP/MVP C#]
http://Dzaebel.NET

.



Relevant Pages

  • Re: Doppelte =?ISO-8859-15?Q?Eintr=E4ge_in_Array_so_schn?= =?ISO-8859-15?Q?ell_wie_m
    ... Frank Dzaebel schrieb: ... die einzelnen Arrays haben. ... [Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences] ... Was ich mit BitArrays gemeint habe ist auf der Seite ...
    (microsoft.public.de.german.entwickler.dotnet.csharp)
  • Re: Math.random
    ... That's not the only possible algorithm; ... without much difficulty implement a long shift-register generator; ... doublevalue or null/undefined/false for auto reseeding, ... I think 0 to 364 would be better; it goes well with zero-based arrays, ...
    (comp.lang.javascript)
  • Re: complex polygon decomposition
    ... As anyone who ever implemented this algorithm and exposed it to real world data knows that the algorithm has issues. ... Namely each time you create an intersection you slightly modify the slope of all affected edges. ... The first solution is tempting because it's just wrapping the algorithm into a simple loop which only gets executed in extreme cases anyway. ... I'm doing decomposition into monotone chains and trinanglate the monotone chains afterwards. ...
    (comp.graphics.algorithms)
  • Re: K random numbers
    ... the second that has the contents of the permutation element. ... Thus, if the first two exchanges are,the arrays ... IIANM Knuth's algorithm S has average time O, ... What does Vitter use for the ...
    (comp.programming)
  • Re: ParallelSort library version 3.0
    ... Let's assume we want to merge sorted arrays X and Y. Select X ... merge algorithm that performs 0.9-5.8 times better than sequential merge, ... In this new version i have implemented a Parallel hybrid ... algorithm approach provides a powerful high performance result. ...
    (alt.comp.lang.borland-delphi)