Wie findet man den häufigsten int in einem 2d-Array von ints?

Question

OK, so dass ich gerade anfangen zu denken, wie ein neues grafisches Plugin für Paint.NET zu implementieren, und ich muss wissen, wie die häufigste ganze Zahl in einem 2d-Array von Ganzzahlen zu finden. Gibt es eine in C# integrierte Möglichkeit, dies zu tun? Oder, hat jemand einen glatten Weg, es zu tun?

Das Array wird etwa so aussehen:

300 300 300 300 300 300 300
  0 150 300 300 300 300 300
  0   0 150 300 300 300 300
  0   0   0   0 300 300 300
  0   0   0   0 150 300 300
  0   0   0   0   0 150 300
  0   0   0   0   0   0 300

Ich müsste wissen, dass 300 die häufigste Zahl in der Reihe ist. Wenn es keine "häufigste" dann geben Sie einfach die zentrale Nummer (die Array-Dimintionen werden immer ungerade x ungerade) 0.

Ich werde dies mit einem "Brute-Force"-Algorithmus implementieren, es sei denn, ihr Experten könnt euch etwas Schnelleres einfallen lassen.

Für jede Hilfe wären wir sehr dankbar.

Danke!

EDIT: Mehr Informationen...

Die Werte werden fast immer SEHR vielfältig sein (noch vielfältiger als mein Beispielfeld). Die Werte werden im Bereich von 0-360 liegen. Die Größe des Arrays wird 5x5 bis etwa 17x17 betragen, je nach Geschwindigkeit des Algorithmus. Das Ergebnis wird für jedes Pixel in einem großen Bild einmal berechnet... schneller ist also besser. ;)

Answer 1

Es ist mindestens O(n*m), egal wie man es betrachtet - man muss sich jede Zelle mindestens einmal ansehen. Der Ort zu sparen ist in, wo Sie die Zählungen der einzelnen Werte akkumulieren, bevor Sie für die häufigste suchen; wenn Ihre Integer über einen relativ kleinen Bereich variieren (sie sind uint16, sagen wir), dann könnten Sie in der Lage sein, einfach ein flaches Array anstelle einer Karte verwenden.

Ich denke, Sie könnten auch eine laufende Zählung durchführen x , y des aktuellen Spitzenkandidaten und des zweitnächsten Kandidaten für "am häufigsten" und vorzeitiges Ausscheiden, sobald weniger als (n*m)-(x-y) Zellen übrig sind, da es zu diesem Zeitpunkt keine Möglichkeit gibt, dass der Zweitplatzierte den Spitzenkandidaten überholt.

Ganzzahlige Operationen wie diese sind ziemlich schnell; selbst für ein Megapixelbild sollte der Brute-Force-Algorithmus nur ein paar Millisekunden benötigen.

Ich bemerke, dass Sie Ihre ursprüngliche Frage bearbeitet haben, um zu sagen, dass der Pixelwert von 0..255 - in diesem Fall definitiv mit einem einfachen flachen Array gehen; das ist klein genug, um leicht in den l1-Dcache passen und ein Lookup in einem flachen Array ist trez schnell.

[Bearbeiten] : Der Umgang mit dem Fall "keine häufigste Zahl" ist sehr einfach, sobald Sie das Histogramm-Array erstellt haben: Sie müssen es nur durchgehen, um die "häufigste" und "zweithäufigste" Zahl zu finden; wenn sie gleich häufig sind, gibt es per Definition keine häufigste Zahl.

const int numLevels = 360; // you said each cell contains a number [0..360)
int levelFrequencyCounts[numLevels]; // assume this has been populated such that levelFrequencyCounts[i] = number of cells containing "i"
int mostCommon = 0, runnerUp = 0;
for (int i = 1 ; i < numLevels ; ++i)
{
  if ( levelFrequencyCounts[i] > levelFrequencyCounts[mostCommon] )
  {
    runnnerUp = mostCommon;
    mostCommon = i;
  }
}

if ( levelFrequencyCounts[mostCommon] != levelFrequencyCounts[runnerUp] )
{
   return mostCommon;
}
else
{
   return CenterOfInputData; // (something like InputData[n/2][m/2])
}

Answer 2

wie würde ich so etwas in C# machen?

Etwa so:

Dictionary<int, int> d = new Dictionary<int, int>();
foreach (int value in matrix)
{
 if (!d.ContainsKey(value))
  d.Add(value, 1);
 else
  d[value] = d[value] + 1;
}
KeyValuePair<int, int> biggest = null;
foreach (KeyValuePair<int, int> found in d)
{
  if ((biggest == null) || (biggest.Value < found.Value))
    biggest = found;
}

Answer 3

Eine Option ist LINQ - ein bisschen ineffizient, aber OK für nicht riesige Arrays:

    var max = (from cell in data.Cast<int>()
               group cell by cell into grp
               select new { Key = grp.Key, Count = grp.Count() } into agg
               orderby agg.Count descending
               select agg).First();
    Console.WriteLine(max.Key + ": " + max.Count);

Oder mit einer gezackten Anordnung:

    var max = (from row in data
              from cell in row
              group cell by cell into grp
              select new {Key = grp.Key, Count = grp.Count()} into agg
              orderby agg.Count descending
              select agg).First();
    Console.WriteLine(max.Key + ": " + max.Count);

In Wirklichkeit würde ich wahrscheinlich ein Wörterbuch/eine Zählung verwenden. Dieses Beispiel ohne LINQ, nur "weil":

    Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (int value in data)
    {
        int count;
        counts.TryGetValue(value, out count);
        counts[value] = count + 1;
    }
    int maxCount = -1, maxValue = 0;
    foreach (KeyValuePair<int, int> pair in counts)
    {
        if (pair.Value > maxCount)
        {
            maxCount = pair.Value;
            maxValue = pair.Key;
        }
    }
    Console.WriteLine(maxCount + ": " + maxValue);

Answer 4

Wenn Geschwindigkeit Ihr Hauptanliegen ist, sollten Sie kein Wörterbuch verwenden. Bleiben Sie bei einem Array von Bytes. Versuchen Sie dies:

// stores hit counts (0-360)
short[] hitCounts = new short[361];

// iterate through 2d array and increment hit counts
for (int i = 0; i < toEvaluate.Length; i++)
{
    for (int j = 0; j < toEvaluate[i].Length; j++)
        hitCounts[toEvaluate[i][j]]++;
}

int greatestHitCount = 0; // the hit count of the current greatest value
int greatest = -1; // the current greatest valeu

// iterate through values (0-360) and evalute hit counts
for (int i = 0; i < hitCounts.Length; i++)
{
    // the hit count of hitCounts[i] is higher than the current greatest hit count value
    if (hitCounts[i] > greatestHitCount)
    {
        greatestHitCount = vals[i]; // store the new hit count
        greatest = i; // store the greatest value
    }
    // there is already a value with the same hit count (which is the greatest)
    else if (hitCounts[i] == greatestHitCount)
        greatest = -1; // there are more than one value, we can't use this if it ends up being the greatest
}

if (greatest >= 0) // no greatest value found
    return greatest;

// figure out the middle x and y value
int x = (toEvaluate.Length - 1) / 2 + 1;
int y = (toEvaluate[x].Length - 1) / 2 + 1;

// return the value at the center of the 2d array as the value
return toEvaluate[x][y];

Wenn Geschwindigkeit wichtiger ist als Lesbarkeit, führt das zwangsläufig zu hässlichem Code. Der obige Code könnte definitiv vom Refactoring profitieren (daher die übertriebenen Kommentare), aber er sollte schnell laufen. Wenn er nicht schnell genug ist, können Sie noch mehr Optimierungen erreichen, indem Sie ihn in nicht verwalteten Code verschieben.

Answer 5

Ihr Bild:

300+ 300+ 300+ 300 300 300 300
  0+ 150+ 300+ 300 300 300 300
  0+   0+ 150+ 300 300 300 300
  0    0    0    0 300 300 300
  0    0    0    0 150 300 300
  0    0    0    0   0 150 300
  0    0    0    0   0   0 300

Die markierten (+) Zahlen sind Ihr Fenster. w,h sind Ihre Fensterabmessungen. anwenden Eimersortierung (wie von anderen vorgeschlagen, da Ihre Wertebereiche recht begrenzt sind). Schneiden Sie Ihre Bewertung nicht auf halber Strecke ab, da Crashworks schlägt vor. Werfen Sie Ihr Ergebnis noch nicht weg. Dies ist der erste Schritt.

300- 300- 300- 300 300 300 300
  0. 150. 300. 300 300 300 300
  0.   0. 150. 300 300 300 300
  0+   0+   0+   0 300 300 300
  0    0    0    0 150 300 300
  0    0    0    0   0 150 300
  0    0    0    0   0   0 300

Verschieben Sie Ihr Fenster. Anstatt zu addieren, subtrahieren Sie die Bereiche in der letzten Zeile/Spalte, die Sie übergeben haben, und fügen die neuen Bereiche hinzu. Auf diese Weise untersuchen Sie jedes Pixel 2(w+h) Mal, d. h. wenn es die Fenstergrenze überschreitet, anstatt w*h Mal, d. h. während sich das Pixel im Fenster befindet, wie bei einer naiven Implementierung.

Mit anderen Worten: Sie müssen Ihr Fenster wie folgt verschieben:

|  ^->|  ^
|  |  |  |
|  |  |  |
V->|  V->|

Ich nehme an, Sie versuchen, einen nichtlinearen Faltungsfilter zu implementieren.

Korrekturen sind willkommen.