Avatar billede rasmuslh Nybegynder
20. juli 2006 - 09:23 Der er 16 kommentarer og
1 løsning

Gennemløb af ArrayList

Hejsa

Jeg har en klasse Node der ser sådan her ud:

public class Node {
   
    private String ip;
    private int SHA;
    private Node successor;
   
    public Node(String ip, int SHA) {
        this.ip = ip;
        this.SHA = SHA;
    }
   
    public void setIP(String ip){
        this.ip = ip;
    }
   
    public String getIP(){
        return ip;
    }
   
    public void setSHA(int SHA){
        this.SHA = SHA;
    }
   
    public int getSHA(){
        return SHA;
    }
   
    public void setSuccessor(Node successor){
        this.successor = successor;
    }
   
    public Node getSuccessor(){
        return successor;
    }
       
}

To af dens felter bliver instantieret i konstruktøren, mens det tredje felt Successor skal instantieres i en metode som jeg har problemer med.

public static void main(String[] args){
   
    //Node node = new Node("192.156.102");
    //System.out.println("IP: " + node.getIP());
    //node.setIP(IpConstructor.generateIP());
    //System.out.println("IP: " + node.getIP());
    //node.setSHA(node.hashIP(node.getIP()));
   
   
   
    ArrayList<Node> list = new ArrayList<Node>();
     
    for (int k = 0 ; k < 10 ; k++) {
       
        list.add(new Node(new Integer(k).toString(), k));

    }
   
    setSuccessorList(list);
   
    for (int j = 0 ; j < list.size() ; j++) {
       
        Node current = list.get(j);
        System.out.println("IP: " + current.getIP()+ " " + current.getSHA() + " " + current.getSuccessor().getSHA());
        System.out.println("IP: " + current.getIP()+ " " + current.getSHA() + " " ); //+ current.getSuccessor().getSHA());
       
    }     

         
} // main

public static void setSuccessorList(ArrayList<Node> list) {   
   
    //setSuccessor
    for (int i = 0 ; i < list.size() ; i++) {
       
        Node current = list.get(i);
        setSuccessor (list, current);           
       
    }
}
   

public static void setSuccessor(ArrayList<Node> list, Node current) {
   
    int SHAcurrent = current.getSHA();
    Node successor = current;
           
    for (int n = 0 ; n < list.size() ; n++) {
   
        //if (n == (list.size()-1)) {
            // current.setSuccessor(current);
        //}
   
        if (successor.getSHA() > (list.get(n).getSHA() - SHAcurrent)) {
       
            current.setSuccessor(list.get(n));
        }
           
    }
   
}

Her er min main metode og de to metoder der skal gennemløbe en arrayList og sætte Successoren på hver Node.

Pt. laver jeg bare 10 Noder i en for-løkke, men meningen er at der skal være X-antal Noder i arraylisten der ikke er sorteret.

Dvs. at når jeg starter min main-metode op skal alle Noder i listen gennemløbes og dens Successor findes.

Successor til en Node er den Node i ArrayListen der har den nærmeste større SHA.

Jeg har brug for et par friske øjne til at se på det.

Håber der er en der kan hjælpe.

Mvh.
Rasmus
Avatar billede Slettet bruger
20. juli 2006 - 11:57 #1
Du kunne jo evt. lade din Node class implementere comparable:

public class Node implements Comparable<Node> {
 
  ...

  public int compareTo(Node o) {
    if (this.getSHA() < o.getSHA())
      return -1;
    if (this.getSHA() == o.getSHA())
      return 0;
    return 1;
  }
}

Du kan så i din main metode sortere listen af nodes inden du tilføjer successors:

public static void main(String[] args) {
 
  ...

  Node[] nodes = new Node[list.size()];
  nodes = list.toArray(nodes);
  Arrays.sort(nodes);   
  for (int i = 0; i < nodes.length; i++) {
    if (i < nodes.length - 1)
      nodes[i].setSuccessor(nodes[i + 1]);
  }   
}

Som jeg læser det du forsøger på vil du for hver node lede listen igennem og finde dens successor. Det tager umiddelbart tid O(n^2). Hvis du sorterer listen med Arrays.sort som anvender en mergesort algoritme er du garanteret tid O(n*log n) på sorteringen. Dvs., O(n + n*log n) = O(n*log n) for hele operationen.
Avatar billede rasmuslh Nybegynder
20. juli 2006 - 12:16 #2
Hej JJust

Tak for inputtet. Det er helt sikkert relevant at overveje. Problemet er lidt at min containeren array'et kun skal bruges til at holde Noderne. Jeg vil gerne lave en hjemmelavet form for simulering af et peer-2-peer net hvor Noderne i ArrayListen skal repræsentere peers.

Da jeg senere ville lave forsøg med tilgang og afgang af noder vil jeg gerne passe på med at blive for afhængig af rækkefølgen af noder.

Desuden er jeg ikke helt med på hvordan din løsning vil fungere ... hvad skal der mere med i main metoden for at få det til at virke.

Undskyld hvis jeg er lidt "langsom".
Avatar billede rasmuslh Nybegynder
20. juli 2006 - 12:19 #3
"Som jeg læser det du forsøger på vil du for hver node lede listen igennem og finde dens successor. " - det er lige præcis det jeg vil.. Der er dog den hale på det at hvis en Node har den højeste SHA skal dens Successor være knuden med den laveste SHA. Altså så der dannes en form for cirkel.
Avatar billede Slettet bruger
20. juli 2006 - 14:16 #4
Kan du ikke prøve at give en lidt mere præcis beskrivelse af det du vil opnå?

Hvordan kommer en peer(node) ind i netværket(bootstrapping)?

En peer skal vel have tildelt sin successor i det øjeblik den kommer på nettet? Så hvordan finder den sin successor?

Du skal vel simulerer et "netværk" ment på den måde at du skal have et central sted du kan sende beskeder til, og som kender til alle dine nodes? Jeg går ud fra at dine peers selv genererer et SHA, som den så sender ud på "nettet"?

Kan du prøve at beskrive dit setup i lidt flere detaljer?

Jeg har engang lavet et projekt på datalogi der minder lidt om det du vil lave: http://www.daimi.au.dk/~just/P2P/report.pdf

Her var peer2peer netværket baseret på Chord!
Avatar billede rasmuslh Nybegynder
20. juli 2006 - 14:26 #5
Det er lige præcis Chord jeg vil prøve at simulere.

Jeg vil prøve at teste i én JVM hvordan Chord fungerer.

Dermed skal der ikke være en decideret p2p netværk. Jeg vil bare prøve at simulere et p2p netværk vha. en række nodes.

Jeg vil prøve at lave en række versioner.

Den første version skal et opslag være vha. en successor. Den næste version skal der bruges et Finger-table osv. Da det er et sommerprojekt er det begrænset hvor meget kan nå.

Det jeg gerne vil undersøge er hvordan Chord performer når den finger-table ikke er up-to-date.

Hidtil har jeg bare en genereret en String IP til hver node ud fra et regexp. SHA's provider interface har jeg ikke fået til at fungere endnu.

Jeg forestiller mig i første omgang at antallet af noden er statistik og vil så løbende udvide det derfra.
Avatar billede rasmuslh Nybegynder
20. juli 2006 - 14:27 #6
I min glæde over at få respons - glemte jeg lige at læse korrektur. Sikke en masse slåfejl. :-)
Avatar billede Slettet bruger
20. juli 2006 - 15:24 #7
Kig her: http://pdos.csail.mit.edu/chord/papers/paper-ton.pdf

Der gives en god beskrivelse i pseudo kode af chord!

Jeg vil foreslå at du laver en Network klasse til simulering af internettet som indeholder følgende:

public class Network {
  private static Node bootStrapPeer = null;
  private static Hashtable<Node> peers = new Hashtable<Node>();

  public static void addBootStrapPeer(Node n) {
    this.bootStrapPeer = n;
    this.addPeer(n);
  }

  public static Node getBootStrapPeer() {
    return this.bootStrapPeer;
  }

  public static addPeer(Node n) {
    this.peers.put(n.getIP(), n); 
  }

  public static String findSuccessor(String IP, Node n) {
    Node contextNode = this.peers.get(IP);
    return contextNode.findSuccessor(n);
  }
}

Den første peer n du laver skal oprette chord-nettet! Dette gøres f.eks. ved at kalde n.create(). Her skal knuden også tilføjes som bootstrap peer: Network.addBootStrapPeer(this).

Alle andre peer's n' kan så få fat på bootstrappen via. Node bootstrap = Network.getBootStrapPeer(). Chord-nettet joines så med et kald: n'.join(bootstrap).

I join metoden kalder Network.findSuccessor(bootstrap.getIP(), this) for at simulerer et remote procedure call.

På hver peer skal være defineret en findSuccessor metode:

public Node findSuccessor(Node n) {
  if (this.getID() < n.getID() && n.getID() < this.successor.getID())
    return this.successor;
  else
    return Network.findSuccessor(this.successor.getIP(), n);
}

Giver det mening?

Ellers skyd mig ned ;)
Avatar billede rasmuslh Nybegynder
20. juli 2006 - 15:44 #8
Jeg skal lige hjem fra arbejde så kigger jeg på det - det kan dog godt være at jeg først poster igen i morgen formiddag. Med min vejleder på ferie er det pragfuldt at finde noget hjælp.

Endnu engang tusind tak for hjælpen. Har læst din opgave igennem.
Avatar billede rasmuslh Nybegynder
21. juli 2006 - 08:42 #9
"Giver det mening?" - både ja og nej.

Jeg kan godt se at jeg bliver nødt til at have en klasse der simulerer selve nettet, men  hvordan styrer jeg størrelse af det net jeg ønsker altså antal peer.

Og hvordan skal BootStrapPeer forstås? Er det et begreb/ting jeg skal have med alene af den årsag af jeg ikke har et rigtigt peer-2-peer eller hvordan skal det opfattes?

Og hvad er grunden til at du bruger en Hashtable frem for ArrayList til at holde nettet?

Sikke mange spørgsmål. Jeg skylder dig en million point efterhånden. Jeg vil gerne oprette en ny post eller donere nogle point til dig.

God weekend

Rasmus
Avatar billede Slettet bruger
21. juli 2006 - 12:07 #10
Der er 2 fordele ved at benytte en Hashtable over ip-adresser i stedet for en ArrayList. Du behøver ikke at lægge en begrænsing på antallet af peers! Dvs., du beregner jo nok din SHA modulo et eller andet stort tal m (for at få det til at give en ring), hvilket giver en naturlig begrænsing i antallet af peers. Hashtabellen svarer så lidt til at lave et opslag i DNS.

Når et p2p-netværk er oprettet skal andre peers have mulighed for at logge på netværket. Den viden hentes normalt igennem f.eks. en hjemmeside som publicerer ip-adresser på peers der allerede er på p2p-netværket, eller kommer evt. som en default indstilling når man downloader peer softwaren. På samme måde skal du have en peer som de andre kender til. Network.getBootStrapPeer er bare en "simulering" af at du henter ip-adresserne fra nettet eller indtaster dem selv i din opsætningsfil til peer'en. Bootstrapping er et begrev der dækker over hvordan en peer får adgang til netværket i første omgang.
Avatar billede rasmuslh Nybegynder
21. juli 2006 - 12:35 #11
Hej jjust

Herligt du er tilbage. :D

Det giver fin mening mht. bootStrapPeer. Hvad sker der hvis Peer der fungerer som bootStrapPeer forsvinder fra nettet.

Jeg har kigget på det kode du lavede igår og har tilpasset det lidt:

Dermed har jeg følgende klasser:

Jeg rettede getID til getSHA da jeg antog at det var den du mente.

public class Node {
   
    private String ip;
    private int SHA;
    private Node successor;
   
    public Node(String ip, int SHA) {
        this.ip = ip;
        this.SHA = SHA;
    }
   
   
    public void setIP(String ip){
        this.ip = ip;
    }
   
    public String getIP(){
        return ip;
    }
   
    public void setSHA(int SHA){
        this.SHA = SHA;
    }
   
    public int getSHA(){
        return SHA;
    }
   
    public void setSuccessor(Node successor){
        this.successor = successor;
    }
   
    public Node getSuccessor(){
        return successor;
    }
   
    public Node findSuccessor(Node n) {
       
          if (this.getSHA() < n.getSHA() && n.getSHA() < this.successor.getSHA()) {
            return this.successor;
          }
          else {
              return Network.findSuccessor(this.successor.getIP(), n);
        }
    }
}

*********************************
Jeg fjernede generics <Node> typen på Hash da jeg fik en fejl angående antallet af argumenter. Desunden var der nogle fejl mht. static kontekst og this, men det skulle vist være korrekt nu.

public class Network {
 
  private static Node bootStrapPeer = null;
  private static Hashtable peers = new Hashtable();

 
  public static void addBootStrapPeer(Node n) {
    Network.bootStrapPeer = n;
    Network.addPeer(n);
  }

  public static Node getBootStrapPeer() {
    return Network.bootStrapPeer;
  }

  public static void addPeer(Node n) {
    Network.peers.put(n.getIP(), n);
  }

  public static Node findSuccessor(String IP, Node n) {
    Node contextNode = (Node)Network.peers.get(IP);
    return contextNode.findSuccessor(n);
  }
 
}

Jeg har også klasserne IPHash og IPConstructor der genererer IP'er og deres SHA-values på baggrund af deres IP, men de er ikke så interessante lige nu.

Nu skal jeg vel så ændre min main-metode så starter et Network?
Avatar billede Slettet bruger
21. juli 2006 - 13:29 #12
Jeg havde ikke testet koden! Den var kun ment som værende vejledende ;)

Metoderne i network er jo statiske, så du behøver vel ikke at starte den op i main metoden? Du mangler en create og join metode i node klassen. Du kan sætte din main til at oprette nodes, og kalde create og join som det passer. Husk at tilføj hver ny knude til netværket med addPeer og addBootStrapPeer!

Mht. hvis bootstrappeer forlader nettet. Tja, nettet eksisterer stadig men det bliver svært at komme på det for en ny node. Hvis der kun er 1 bootstrappeer er det jo single point of failure, men du kan jo evt. lave en electionsprotocol mellem de resterende peers så en ny bootstrappeer bliver valgt, eller du kan have en liste af bootstrappeers...det er op til dig selv! Du behøver forøvrigt ikke at genererer SHA'er på baggrund af IP addresserne. Du kan bare bruge tilfældige tal. Så længe det interval du vælger SHA's fra er så stort at sandsynligheden for en clash er meget lille giver det ingen problemer!
Avatar billede Slettet bruger
21. juli 2006 - 13:32 #13
Åh ja, generics koden gav problemer fordi Hashtable forventer at man angiver typen på både key og value, så hvis du bruger new Hashtable<String><Node>() skulle det virke!
Avatar billede rasmuslh Nybegynder
21. juli 2006 - 14:15 #14
"Jeg havde ikke testet koden! Den var kun ment som værende vejledende ;)"

Hvad er nu det for noget - totalt for dårligt. :D

Hvad er formålet med at have en create og join metode? Er det bare for at undgå at kalde konstruktøren direkte.

addBootStrapPeer skal vel kun kaldes en gang når netværket genereres første gang?

Jeg har foreløbigt lavet denne main metode til at teste det:

    public static void main(String[] args) {
       
        Network test = new Network();
        IpConstructor ip = new IpConstructor();
        test.addBootStrapPeer(new Node(ip.generateIP(), 1)); // Andet argument skal med tiden genereres vha. SHA 
       

        for (int k = 0 ; k < 50 ; k++) {
           
            test.addPeer(new Node(ip.generateIP(), k));

        }
    }
Avatar billede rasmuslh Nybegynder
24. juli 2006 - 11:23 #15
Hej jjust

Jeg har siddet og roddet med mit projekt hele weekenden og er kommet frem til at jeg ikke helt forstår den sammenhæng du har mellem findSuccessor(Integer SHA, Node N) i Network-klassen og findSuccessor(Node n) og join(bootstrap) i Node-klassen.

Mit problem er at jeg ikke forstår hvorfor der laves et rekursivt kald i else-delen i findSuccessor(Node n) i Node-klassen.

Jeg har de her metoder:

Node-klassen:

    public void join(bootstrap){
        Network.findSuccessor(bootstrap.getIP(), this);
    }

    public Node findSuccessor(Node n) {
          if (this.getSHA() < n.getSHA() && n.getSHA() < this.successor.getSHA()) {
                    return this.successor;
          }
          else {
              return Network.findSuccessor(this.successor.getSHA(), n);
        }
    }

Network-klassen:

      public static Node findSuccessor(Integer SHA, Node n) {
       
            Node contextNode = Network.peers.get(SHA);
        return contextNode.findSuccessor(n);
     
          }

Jeg håber virkelig meget at du gider / har tid til at forklare med ord hvordan Successoren til en given Node i din fremgangsmåde.

Jeg vil meget gerne sende en flaske vin afsted til dig hvis du gider hjælpe. Jeg er temmelig desperat for at få noget virkende kode efterhånden. :)

Du kan evt. sende mig en mail på rasmuslh AD gmail DOT com
Avatar billede rasmuslh Nybegynder
12. august 2006 - 17:53 #16
@JJust - smider du ikke et svar og får de point du er mere end fortjent til?
Avatar billede rasmuslh Nybegynder
13. juni 2008 - 15:14 #17
Hmmmh - lukker den selv så.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester