2-dimensionale Array vs einfache Array

Ich würde gerne wissen, was zur Ausführungszeit schneller wäre und welche weniger Speicher als die andere Lösung kostet.2-dimensionale Array vs einfache Array

Ich habe ein Sudoku gemacht, als ich diese Frage selbst gestellt habe. Wie Sie wissen, ist Sudoku ein 9 x 9 Rasterfeld und im Allgemeinen implementieren alle Solver um Sudoku Array [9] [9]. Ich nehme an, es liegt daran, dass es wie das Gitter aussieht, das Sie spielen.

Meine Frage ist einfach, wie das Raster immer ein Quadrat (ex: 9x9), was ist der schnellste und am niedrigsten Speicherverbrauch zwischen: - 2Dimensions: Array [9] [9] - Einzel Dimension: Array [81 ]

Der Zugriff auf Werte wird in beiden Fällen berechnet (wenn Array bei Index 0 beginnt und Sie die 5. Spalte und 6. Zeile in einem 9x9-Raster benötigen): - Koordinatenpaar für 2D-Array (zB Array [5-1 ] [6-1]) - einzelne berechnete Position (Array [((6-1) * 9) + (5-1)])

Gibt es Möglichkeiten, dies zu testen?

Quelle

2016-10-09 aviel

Machen Sie sich deswegen keine Sorgen. Verwenden Sie einfach die Struktur, die für den Algorithmus am bequemsten ist. Wenn Sie nicht über Millionen von Gittern verfügen, wird das keinen Unterschied machen. – Barmar

Aber um Ihre Frage zu beantworten, wird ein einzelnes Array weniger Speicher, da es nur 81 Werte enthält, während das Array von Arrays 81 Werte und 9 Zeiger enthält. – Barmar

Natürlich ist das, was ich mir selbst gesagt habe, aber einfach Neugier, wenn eines Tages, wenn die Grössen des Gitters hoch sind, es einen Unterschied geben sollte – aviel

Wie in den Kommentaren erwähnt die ein Array-Ansatz die günstigste (Speicher weise)

In Bezug auf Geschwindigkeit, timeit ist dein Freund:

import timeit 



one_array = timeit.timeit(setup="a = [0]*81;s=3;x=2;y=1;", stmt='a[s*9+y*3+x]') 
multi_array = timeit.timeit(setup="a = [[[0]*3]*3]*9;s=3;x=2;y=1;", stmt='a[s][x][y]') 


print (one_array) 
print (multi_array) 
if one_array < multi_array: 
    print('one_array is faster') 
else: 
    print("multi_array is faster!")

0,21741794539802967

0,13626013606615175

multi_array ist schneller!

zumindest in Python ...

Quelle

2016-10-09 19:04:15

2-dimensionale Array vs einfache Array

Antwort

Verwandte Themen