Wie summiert man die Dimensionen eines zur Laufzeit angegebenen Arrays?

Question

Ich arbeite an einer Funktion zur Bestimmung der Entropie einer Verteilung.Es verwendet eine Copula, falls jemand damit vertraut ist.Ich muss die Werte im Array basierend darauf zusammenfassen, welche Dimensionen „beachtet“ werden.

Beispiel:Betrachten Sie das folgende Beispiel...

Dimension 0 (across)
_ _ _ _ _ _ _ _ _ _ _ _ _
|_ 0 _|_ 0 _|_ 0 _|_ 2 _|  Dimension 1
|_ 1 _|_ 0 _|_ 2 _|_ 0 _|   (down)
|_ 0 _|_ 3 _|_ 0 _|_ 6 _|
|_ 0 _|_ 0 _|_ 0 _|_ 0 _|

I "care about" dimension 0 only, and "don't care" about the rest (dim 1).
Summing this array with the above specifications will
"collapse" the "stacks" of dimension 1 down to a single 4 x 1 array:

_ _ _ _ _ _ _ _ _ _ _ _ _ 
|_ 1 _|_ 3 _|_ 2 _|_ 8 _|

This can then be summed, or have any operation performed.

Ich muss dies mit einem Array von „n“ Dimensionen tun, was durchaus 20 sein könnte.Außerdem muss ich dazu in der Lage sein, bestimmte Dimensionen zu berücksichtigen und den Rest zu reduzieren.Mir fällt das besonders schwer, weil ich mir keine 20 Dimensionen vorstellen kann :p .Wenn mir jemand helfen könnte, C/C++-Code zum Kollabieren/Summieren einzurichten, wäre ich sehr, sehr dankbar.

Aktualisieren:

Bin gerade nach Hause gekommen.Hier sind einige Informationen zur Beantwortung Ihrer Fragen:

1. Tut mir leid, dass ich die Änderungen rückgängig gemacht habe. Ich hatte gehofft, wenn ich auf „Zurücksetzen“ klicke, würden mir die Änderungen angezeigt, damit ich sehen kann, was ich vermasselt habe, ein bisschen wie bei Wikipedia.Das war nicht der Fall, wie ich herausfand.
2. @jeff – Was macht keinen Sinn?Ich nutze diesen großartigen Service aus (meiner Meinung nach) legitimen Gründen.Ich möchte in meinem Hobby, das alles ist, besser werden, da ich in der Highschool bin.Viele meiner Beiträge befassen sich mit der Implementierung eines genetischen Algorithmus (Dieser Beitrag, Sparsarray, Rang eines Arrays, Zeigermanipulation).
3. Ich verwende eine spärliche Array-Darstellung, da es mit einem herkömmlichen (dichten) Array möglich ist, die Anzahl der Moleküle im Universum zu überschreiten.Im Moment spielt die Implementierung des Sparsarrays selbst keine große Rolle, da ich daran arbeite, dass es mit einem Standardarray funktioniert, bevor ich zu einer Sparse-Darstellung übergehe.Für diejenigen, die meine vorherigen Fragen nicht gesehen haben: Ich verwende einen binären Suchbaum als Struktur, um die spärlichen Array-Punkte zu enthalten, und eine „Treiber“-Funktion, um den Baum nach Bedarf zu durchlaufen und alles zurückzugeben, wozu die Funktion entwickelt wurde.Dies ist flexibel, sodass ich viele verschiedene Methoden für den Zugriff auf das Array berücksichtigen kann.
4. Die Struktur ist ein Hyperwürfel, und die Anzahl der Dimensionen wird zur Laufzeit angegeben, ebenso wie die Länge jeder Dimension (die alle gleich sind, da es sich um einen Hyperwürfel handelt).

Vielen Dank an alle für Ihren Beitrag.

Answer 1

Dies könnte Anwendungen haben.Nehmen wir an, Sie haben ein 2D-Conway-Spiel des Lebens implementiert (das eine 2D-Ebene definiert, 1 für „lebendig“, 0 für „tot“) und Sie haben den Spieleverlauf für jede Iteration gespeichert (was dann einen 3D-Würfel definiert).Wenn Sie wissen möchten, wie viele Bakterien im Laufe der Geschichte am Leben waren, würden Sie den oben genannten Algorithmus verwenden.Sie könnten denselben Algorithmus für eine 3D-Version (und 4D, 5D usw.) des Game of Life-Rasters verwenden.

Ich würde sagen, das war eine Frage zur Rekursion. Ich bin noch kein C-Programmierer, aber ich weiß, dass es in C möglich ist.In Python,

def iter_arr(array):
  sum = 0
  for i in array:
    if type(i) == type(list()):
      sum = sum + iter_arr(i)
    else:
      sum = sum + i
  return sum 

1. Durchlaufen Sie jedes Element im Array
2. Wenn das Element ein anderes Array ist, rufen Sie die Funktion erneut auf
3. Wenn das Element kein Array ist, addieren Sie es zur Summe
4. Rückgabesumme

Anschließend wenden Sie dies auf jedes Element in der Dimension „Umsorge“ an.

Dies ist jedoch in Python aufgrund der Ententypisierung einfacher ...

Answer 2

@Jeff

Ich denke tatsächlich, dass das eine interessante Frage ist.Ich bin mir nicht sicher, wie nützlich es ist, aber es ist eine berechtigte Frage.

@Ed

Können Sie etwas mehr Informationen zu dieser Frage geben?Sie sagten, die Dimension des Arrays sei dynamisch, aber ist die Anzahl der Elemente auch dynamisch?

BEARBEITEN:Ich werde trotzdem versuchen, die Frage zu beantworten.Ich kann Ihnen den Code nicht spontan geben (es würde eine Weile dauern, ihn ohne Compiler hier auf diesem PC richtig hinzubekommen), aber ich kann Ihnen den richtigen Weg weisen ...

Nehmen wir als Beispiel 8 Dimensionen (0-7) mit den Indizes 0 bis 3.Sie interessieren sich nur für 1,2 und 6.Das bedeutet, dass Sie zwei Arrays haben.Erste, array_care[4][4][4] für 1,2 und 6.Der array_care[4][4][4] wird das Endergebnis enthalten.

Als nächstes wollen wir auf ganz bestimmte Weise iterieren.Wir haben das Array input[4][4][4][4][4][4][4][4] zu analysieren, und wir kümmern uns um die Dimensionen 1, 2 und 6.

Wir müssen einige temporäre Indizes definieren:

int dim[8] = {0,0,0,0,0,0,0,0};

Wir müssen auch die Reihenfolge speichern, in der wir die Indizes erhöhen möchten:

int increase_index_order[8] = {7,5,4,3,0,6,2,1};
int i = 0;

Diese Reihenfolge ist wichtig, um das zu tun, was Sie angefordert haben.

Definieren Sie ein Beendigungsflag:

bool terminate=false;

Jetzt können wir unsere Schleife erstellen:

while (terminate)
{
array_care[dim[1]][dim[2]][dim[6]] += input[dim[0]][dim[1]][dim[2]][dim[3]][dim[4]][dim[5]][dim[6]][dim[7]];

while ((dim[increase_index_order[i]] = 3) && (i < 8))
{
dim[increase_index_order[i]]=0;
i++;
}

if (i < 8) {
dim[increase_index_order[i]]++; i=0;
} else {
terminate=true;
}
}

Das sollte für 8 Dimensionen funktionieren und sich um 3 Dimensionen kümmern.Es würde etwas mehr Zeit in Anspruch nehmen, es dynamisch zu gestalten, und ich habe keine Zeit dafür.Hoffe das hilft.Es tut mir leid, aber ich habe die Code-Markups noch nicht gelernt.:(

Answer 3

So etwas ist viel einfacher, wenn Sie STL-Container verwenden, oder vielleicht Boost.MultiArray.Wenn Sie jedoch ein Array verwenden müssen:

#include <iostream>
#include <boost/foreach.hpp>
#include <vector>

int sum(int x) {
    return x;
}

template <class T, unsigned N>
int sum(const T (&x)[N]) {
    int r = 0;
    for(int i = 0; i < N; ++i) {
        r += sum(x[i]);
    }
    return r;
}

template <class T, unsigned N>
std::vector<int> reduce(const T (&x)[N]) {
    std::vector<int> result;
    for(int i = 0; i < N; ++i) {
        result.push_back(sum(x[i]));
    }
    return result;
}

int main() {
    int x[][2][2] = {
        { { 1, 2 }, { 3, 4 } },
        { { 5, 6 }, { 7, 8 } }
    };

    BOOST_FOREACH(int v, reduce(x)) {
        std::cout<<v<<"\n";
    }
}

Answer 4

Tatsächlich haben Sie durch das Reduzieren der Spalten diese bereits summiert, sodass die Dimension für Ihr Beispiel überhaupt keine Rolle spielt.Habe ich etwas verpasst oder du?

Answer 5

Ich denke, das Beste, was man hier tun kann, wäre eines oder beide von zwei Dingen:

1. Überdenken Sie das Design. Wenn es zu komplex ist, finden Sie einen weniger komplexen Weg.
2. Hören Sie auf, es sich vorzustellen.:P Speichern Sie einfach die betreffenden Dimensionen, die Sie summieren möchten, und führen Sie sie dann einzeln aus.Sobald Sie den Basiscode haben, können Sie die Effizienz Ihres Algorithmus verbessern.

Answer 6

Da bin ich anderer Meinung, es gibt IMMER einen anderen Weg.

Und wenn Sie wirklich kann nicht Refactor, dann müssen Sie das Problem in kleinere Teile zerlegen.Wie ich schon sagte: Legen Sie fest, welche Dimensionen Sie summieren müssen, und treffen Sie sie dann einzeln.

Hören Sie außerdem auf, die Änderungen zu ändern, sie korrigieren Ihre Rechtschreibfehler und versuchen, Ihnen zu helfen ;)

Answer 7

Du machst das in c/c++...Sie haben also ein Array von Arrays von Arrays ...Sie müssen nicht 20 Dimensionen visualisieren, da die Daten nicht so im Speicher angeordnet sind, für eine zweidimensionale:

[1] --> [1,2,3,4,5,6,...]
[2] --> [1,2,3,4,5,6,...]
[3] --> [1,2,3,4,5,6,...]
[4] --> [1,2,3,4,5,6,...]
[5] --> [1,2,3,4,5,6,...]
 .           .
 .           .
 .           .

Warum können Sie also nicht die erste Iteration durchlaufen und deren Inhalt zusammenfassen?Wenn Sie versuchen, die Größe herauszufinden, dann sizeof(array)/sizeof(int) ist ein riskanter Ansatz.Sie müssen die Dimension kennen, um diese Daten verarbeiten zu können, und den Speicher einrichten, damit Sie die Tiefe der zu summierenden Rekursion kennen.Hier ist ein Pseudocode dessen, was Sie anscheinend tun sollten:

sum( n_matrix, depth )
  running_total = 0
  if depth = 0 then
    foreach element in the array
      running_total += elm
  else 
     foreach element in the array
       running_total += sum( elm , depth-1 )
  return running_total

Answer 8

x = number_of_dimensions;
while (x > 1)
{
  switch (x)
  {
    case 20:
      reduce20DimensionArray();
      x--;
    break;
    case 19:
      .....
  }
}

(Entschuldigung, ich konnte nicht widerstehen.)

Answer 9

Wenn ich das richtig verstehe, möchten Sie alle Werte im Querschnitt summieren, der in jedem „Bin“ entlang einer Dimension definiert ist.Ich schlage vor, ein 1D-Array für Ihr Ziel zu erstellen und dann jedes Element in Ihrem Array zu durchlaufen und den Wert mit dem Index der interessierenden Dimension zum Ziel hinzuzufügen.

Wenn Sie eine beliebige Anzahl von Dimensionen verwenden, müssen Sie über eine Möglichkeit verfügen, Elemente anzusprechen (ich wäre neugierig, wie Sie dies implementieren).Ihre Implementierung wirkt sich darauf aus, wie Sie den Zielindex festlegen.Ein offensichtlicher Weg wäre jedoch die Überprüfung von if-Anweisungen in den Iterationsschleifen.

Answer 10

Wenn Sie sagen, dass Sie nicht wissen, wie viele Dimensionen es gibt, wie genau definieren Sie dann die Datenstrukturen?

Irgendwann muss jemand dieses Array erstellen und dazu muss er die Abmessungen des Arrays kennen.Sie können den Ersteller zwingen, diese Daten zusammen mit dem Array zu übergeben.

Es sei denn, die Frage besteht darin, eine solche Datenstruktur zu definieren ...