[Java] Array van lijsten?

[Verwijderd]

Hoi, ik ben een beginner met Java. Ik zou graag willen weten hoe ik een array van objects (bv lijsten) maak?
Bv dat bij de volgende input (uit bv. een tekstfile):

1. 2 3 4
2. 1 3 4
3. 1 2 4
4. 1 2 3 5
5. 6 7 8
6. 4 5 7
7. 5 6 8
8. 5 7

ik een soort bucket-array (van 8 elementen) kan maken?

[chris]

Kan je niet gewoon zeggen:

Java:

int[][] container = new int[8][4];

dan heb je een 8x4 twee-dimensionale array.

[Verwijderd]

chris schreef op dinsdag 15 januari 2008 @ 00:53:
Kan je niet gewoon zeggen:

Java:

int[][] container = new int[8][4];

dan heb je een 8x4 twee-dimensionale array.

Ja, maar ik zou graag in O(1) tijd elementen willen toevoegen en weghalen in de bucket...

[Ontspannen]

Vaag taal gebruik?

Wat je eventueel zou kunnen:

// Array van 10 elementen
int[] array = new int[10];

Iedere gelezen waarde in het document staat dan voor een index van een element van de array
en betreffend element met 1 verhogen.
Stel getal 9 wordt uit het document gelezen dan:

// betreffend element met 1 verhogen
array[9] = array[9] + 1;

Heb je alle waarden uit het document gelezen, hoef je alleen het array door te lopen
voor te kijken hoeveel je van iedere waarde hebt.

Bucket sort heet dat geloof ik.

?

[Ivo]

code:

List[] a = new List[42];
for (int i = 0; !EOF; ++i) {
  List l =new List();
  while (!newline) {
    l.add(inputchar);
  }
  a[i] = l;
}

Zoiets wil je doen?

Edit: Ik ga ervan uit dat de lijst-implementatie in Java toelaat dat elementen in O(1) tijd kunnen worden toegevoegd. Het lijkt me stug als dit niet zo is.

[ Voor 29% gewijzigd door Ivo op 15-01-2008 07:48 ]

[Robtimus]

Het is niet zo.

Even uitgebreider:

Je hebt 2 typen Lists standaard in Java: een ervan gebruikt een array op de achtergrond (ArrayList, Vector), de ander is een linked list (LinkedList).

ArrayList en Vector zijn O(1) voor toevoegen, mits:
a) je alleen aan het einde toevoegt. Zo niet, dan moet alles wat erna komt opgeschoven worden. Verder kan probleem b) ook nog eens voorkomen.
b) het interne array niet vol is. Er wordt een nieuw array gecreeerd, meestal 2x zo groot, en ALLES wordt daarnaartoe gekopieerd. Weliswaar dmv de native (dus snellere) System.arraycopy call, maar toch.

LinkedList kan wel degelijk in O(1) toevoegen, aan het begin of het einde. Voor elke andere positie moet eerst deze positie worden opgezocht, waarna er wel in O(1) het element toegevoegd wordt. Dat opzoeken kan echter O(n) zijn, omdat hij maximaal n/2 plekken moet afgaan.

[YopY]

b) het interne array niet vol is. Er wordt een nieuw array gecreeerd, meestal 2x zo groot, en ALLES wordt daarnaartoe gekopieerd. Weliswaar dmv de native (dus snellere) System.arraycopy call, maar toch.

Kleine optimalisatie daarbij: Als je weet hoe groot de lijst ongeveer zal worden (in deze zaak dus het aantal rijen van het bestand, ook al zul je die, indien je het een beetje geheugen-efficient wilt programmeren, niet weten), kun je met een secundaire constructor de initiele grootte instellen. Anderzijds kun je de ensureCapacity() methode aanroepen, waarmee de grootte van de interne array aangepast wordt zodat hij ten minste het aantal elementen kan bevatten die je als argument meegeeft aan de parameter.

[Polichism]

Ik heb voor school ook een opdracht moeten maken met een 2D Array.
Hier mijn progsel met lijsten in een Array:

Java:

      import java.util.ArrayList;
      import java.util.Random;
       
      public class sumRowCol
      {
          private int[][] data;
          private Random generator;
         
          public sumRowCol(int x, int y)
          {
              data = new int[x][y];
              generator = new Random();
             
              for(int i=0; i<x; i++)
              {
                  for(int k=0; k<y; k++)
                  {
                      data[i][k] = generator.nextInt(16);
                  }
              }
          }
          public int getDataRow(int x)
          {
              int sum = 0;
              for(int i=0; i< data.length; i++)
              {
                  sum += data[x][i];
              }
              return sum;
           }
           public int getDataCol(int x)
           {
              int sum = 0;
               for(int i=0; i<data.length; i++)
               {
                   sum += data[i][x];
               }
               return sum;
         }
      } 

[ Voor 34% gewijzigd door Polichism op 16-01-2008 11:07 ]

[pedorus]

Hm, als de ordening in de buckets niet uitmaakt en je geen dubbelen hebt, zou ik een HashSet gebruiken. HashSet is praktisch gezien bijna O(1) bij toevoegen/verwijderen/opzoeken/alles afgaan. (Alleen als de grootte van de onderliggende datastructuur onjuist is of de hash-functie niet goed werkt op de data is dit niet zo.) Vector is al besproken. Dus iets als:

Java:

Vector <HashSet<Integer>> data = new Vector <HashSet<Integer>>();

Je moet dan wel die Vector even vullen met nieuwe HashSets, bijvoorbeeld bij het inlezen:

Java:

Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
    HashSet<Integer> hs = new HashSet<Integer>();
    StringTokenizer st = new StringTokenizer(sc.next());
    while (st.hasMoreTokens()) {
         hs.add(new Integer(st.nextToken()));
     }
    data.add(hs);
}

De java API heeft meer documentatie (tenminste versie 1.5).

[prototype]

pedorus schreef op woensdag 16 januari 2008 @ 14:09:
Hm, als de ordening in de buckets niet uitmaakt en je geen dubbelen hebt, zou ik een HashSet gebruiken. HashSet is praktisch gezien bijna O(1) bij toevoegen/verwijderen/opzoeken/alles afgaan. (Alleen als de grootte van de onderliggende datastructuur onjuist is of de hash-functie niet goed werkt op de data is dit niet zo.) Vector is al besproken. Dus iets als:

Java:

Vector <HashSet<Integer>> data = new Vector <HashSet<Integer>>();

Je moet dan wel die Vector even vullen met nieuwe HashSets, bijvoorbeeld bij het inlezen:

Java:

Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
    HashSet<Integer> hs = new HashSet<Integer>();
    StringTokenizer st = new StringTokenizer(sc.next());
    while (st.hasMoreTokens()) {
         hs.add(new Integer(st.nextToken()));
     }
    data.add(hs);
}

De java API heeft meer documentatie (tenminste versie 1.5).

Paar opmerkingen:

• Vector implementeert welliswaar List, maar itt andere classes die List ook implementen is deze synchronized (thread-safe). Als je dit niet nodig hebt, dan volstaat een ArrayList ook (immers goedkoper door het ontbreken van synchronisatie, moet je natuurlijk wel de juiste ensurecapacity gebruiken om O(1) te bewerkstelligen voor add en get).
• Waarom gebruik je hier zo'n enorm concrete declarative type? Je programmeert nu tegen exact dezelfde interface aan als de implementatie en dat heeft alleen nut als je ook echt wil dat die interface, die van de implementatie is (i.e. je gebruikt iets uit de interface dat niet abstracter gedefinieerd is). In dit geval zou ik zeggen dat abstractie wenselijk is, aangezien je niks speciaals gebruikt van HashSet specifiek (als daar al uberhaupt verschil in zit met de interface van Set):
  
  Java:
  

  HashSet<Integer> bla = new HashSet<Integer>();

  
  
  Zou ik dan vervangen met:
  
  Java:
  

  Set<Integer> bla = new HashSet<Integer>();

  
  
  Het wordt iets ingewikkelder bij een nested generic:
  
  Java:
  

  List<Set<Integer>> foobar = new ArrayList<HashSet<Integer>>();

  
  Gaat niet werken en hiervoor moet je je even inlezen in type systems, en met name invariantie en covariantie van typen. In dit geval moet je ipv Set iets nemen dat covariant is aan set:
  
  Java:
  

  List<? extends Set<Integer>> foobar = new ArrayList<HashSet<Integer>>();

  
  
  Mocht je later een andere implementatie van een list of set willen hebben voor "bla" dan hoef je het alleen maar aan te passen in deze regel...
• Duurder in iig geheugen complexiteit doordat je nu met wrapper klassen (e.g. Integer) voor generics werkt ipv de primitive types (int). In je geheugen zit nu een heel Integer object dan voor elk unieke integer die je gebruikt ipv een paar bytes voor de primitive representatie ervan, met references ernaar als de mensen bij java intern hebben geoptimaliseerd met zoiets als flyweight pattern (dat ze vast wel hebben gedaan).

[voodooless]

Je kunt ook eens kijken naar de Collection implementaties van de Javalution lib: Ze zijn erg snel en speciaal gemaakt voor time constrained toepassingen.