Java: quel est le big-O temps de déclarer un tableau de taille n?

Qu'est-ce que le temps d'exécution de déclarer un tableau de taille n en Java? Je suppose que cela dépendra de savoir si le mémoire est remis à zéro sur la collecte des ordures (auquel cas il pourrait être O(1) ) ou lors de l'initialisation (auquel cas il faudrait que ce soit O(n) ).

Je pense que ce serait JVM dependend
Je suppose que la langue-dans-joue, pédant réponse est que c'est O(1) parce que même si c'est O(n), n est délimitée par 2^31 pour Java tableaux et donc sera asymptotiquement plus faible que certaines des grandes constante.
dans ce cas, chaque calcul est O(1) de l'espace, puisque le nombre d'atomes sur terre est finie. 😛
eh bien, placez une autre façon, depuis que l'ordinateur a fini de mémoire, toute la résiliation de programme, exécutez en O(1).
Darn, la réponse pourrait m'avez sauvé beaucoup de maux de tête dans l'uni! Oui, évidemment, c'était un commentaire ridicule.
Merci pour toutes ces excellentes informations. Je souhaite que je pourrais accepter toutes vos réponses!

InformationsquelleAutor Mala | 2011-04-12

18

C'est O(n). Considérons ce programme simple:
```
public class ArrayTest {

  public static void main(String[] args) {
     int[] var = new int[5];
  }

}
```
Le bytecode généré est:
```
Compiled from "ArrayTest.java"
public class ArrayTest extends java.lang.Object{
public ArrayTest();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_5
   1:   newarray int
   3:   astore_1
   4:   return

}
```
L'instruction de prendre un coup d'oeil à est la newarray instruction (il suffit de chercher pour newarray). À partir de la VM Spec:

Un nouveau tableau dont les éléments sont de type atype et de longueur comte est alloué à partir des déchets collectés sur le tas. Une référence arrayref à ce nouvel objet array est poussé dans l'opérande de la pile. Chacun des éléments du tableau est initialisé par défaut à la valeur initiale pour le type de la matrice (§2.5.1).

Étant donné que chaque élément est initialisé, il faudrait O(n) temps.

MODIFIER

Regardant le lien amit, il est possible de mettre en œuvre de la matrice de l'initialisation avec une valeur par défaut, en temps constant. Donc je suppose que cela dépend en définitive de la JVM. Vous pourriez faire un peu rugueuse d'analyse comparative pour voir si c'est le cas.
- amit a posté un lien vers @Jonathan réponse de pour savoir comment vous pourriez faire l'initialisation tardive au sein de la JVM code. Je ne vois pas comment elle allait se briser les spec de le faire, aussi longtemps que du POV de la matrice de l'interface (lit et écrit) le tableau est initialisé avec les valeurs correctes.
- Peters, intéressant. Je suppose que cela dépend de si particulier JVM met en œuvre à l'aide de la lazy-méthode d'initialisation ou pas. Assez cool algorithme!
- Oui, il est. La seule inquiétude que j'aurais serait de savoir si il est possible de le faire et aussi permettre à des méthodes indigènes d'interagir avec un tableau via JNI.
- Vrai. Si JNI offre un accès direct à la matrice, alors ce pourrait être un problème parce que les emplacements contiennent des données incorrectes.
InformationsquelleAutor Vivin Paliath
8

Un petit aucun de référence pour les professionnels sur JRE1.6:
```
public static void main(String[] args) {
    long start = System.nanoTime();
    int[] x = new int[50];
    long smallArray = System.nanoTime();
    int[] m = new int[1000000];
    long bigArray = System.nanoTime();
    System.out.println("big:" +  new Long( bigArray - smallArray));
    System.out.println("small:" +  new Long( smallArray - start));


}
```
a donné le résultat suivant:
```
big:6133612
small:6159
```
donc je suppose que O(n).
bien sûr, il n'est pas assez pour être sûr, mais c'est un indice.
- -1 pour microbenchmarks, +10 pour le commentaire sur @Jonathan post.
- pour le -1: je suis d'accord, microbenchmarking est le diable. c'est pourquoi j'ai indiqué, rien n'est concluant et c'est très non-proffesional, je voulais juste donner un indice pour poursuivre la discussion. merci pour le +10.
- Le plus grand tableau est 2000 fois plus grande, alors qu'il faut seulement 1000 fois plus de temps. Alors, êtes-vous sûr que c'est de O(n)? Je ne sais rien à propos de big-o, mais pour moi, ça ressemble: O(n/2)
- est encore O(n) je.e, toujours linéaire 🙂
- O(n/2) = O(n). Aussi, vous pouvez supposer qu'il y a certains frais généraux, communs aux deux initialisations, indépendamment de la taille... et comme je l'ai dit, cette "référence" ne prouve rien, c'est juste suggère que la taille de la matrice a une incidence sur les temps d'initialisation, et le O(n) est juste une hypothèse.
- le code est exécuté en interpréter le mode w/ zero optimisations, que ce soit. Écrit microbenchmarks en java est dur
- pour être juste, vous pouvez dessiner à peu près tout de la fonction par le biais de deux points aussi facilement qu'une ligne 😉
- le temps peut-être seulement causée par trouver et d'allouer plus d'espace. et avez-vous testé sur tous les types de JVM. et une JVM en vertu de chaque état?
InformationsquelleAutor amit
4

Je suis assez sûr que c'est O(n), que la mémoire est initialisée lorsque le tableau est alloué. Il ne devrait pas être plus élevé que O(n), et je ne vois aucun moyen de faire moins de O(n), de sorte que semble la seule option.

De fournir plus de précisions, Java initialise les tableaux sur la répartition. Il n'y a aucun moyen de zéro une région de la mémoire sans marcher à travers elle, et la taille de la région détermine le nombre d'instructions. Par conséquent, la limite inférieure est O(n). Aussi, il n'aurait aucun sens d'utiliser un algorithme de mise à zéro plus lent que linéaire, puisqu'il y a un linéaire de la solution, de sorte que la limite supérieure doit être en O(n). Par conséquent, O(n) est la seule réponse qui a du sens.

Juste pour le plaisir, mais, imaginez un étrange morceau de matériel où l'OS a le contrôle sur le pouvoir de différentes régions de la mémoire et peut-zéro d'une région par un retournement de l'éteindre puis sur. Cela semble comme il serait O(1). Mais la région ne peut être si grand avant de l'utilitaire disparaît (ne voudrais pas tout perdre), afin de demander à zéro une région sera toujours en O(n) avec un grand diviseur.
- voici une façon de le faire mieux (en termes de big O) eli.thegreenplace.net/2008/08/23/... - je n'ai aucune idée de comment la machine fonctionne réellement
- la JVM peut décider de ne pas à zéro la mémoire si peut être prouvé, il est d'abord écrit/puis lire. Tableau.clone. Système.arraycopy, Tableaux.copyOf et ainsi de suite.
- C'est assez cool. Je doute que la JVM ne qui, en raison de la grande quantité de frais généraux, mais encore frais. @bestsss Bon point. J'ai été en supposant que le cas général de déclarer type[len] array;
- Vous pouvez utiliser un contrôleur de DMA à cette fin. Il est toujours en O(n), mais le CPU peut aller faire autre chose en attendant.
- la JVM essaie de supprimer même les limites de contrôles à des tableaux, la méthode proposée est plus inefficace (en plus de microbenchmarks) pour usages généraux.
- Je pense qu'il n'est pas de même pour le processus d'int[n] , Entier[n], SomeObject[n]
InformationsquelleAutor Jonathan

Disons simplement le tester.

class ArrayAlloc {
  static long alloc(int n) {
    long start = System.nanoTime();
    long[] var = new long[n];
    long total = System.nanoTime() - start;
    var[n/2] = 8;
    return total;
  }
  public static void main(String[] args) {
    for(int i=1; i<100000000; i+=1000000) {
      System.out.println(i + "," + alloc(i));
    }
  }
}

Et les résultats sur mon linux ordinateur portable (i7-4600M @ 2.90 GHz):

Java: quel est le big-O temps de déclarer un tableau de taille n?

Donc il est clair ressemble O(n), mais il ressemble également à celui-ci passe d'une méthode plus efficace à près de 5 millions d'éléments.

InformationsquelleAutor lovasoa

Vous devez vous connecter pour publier un commentaire.