[Java]Efficient zoeken in grote vectoren

[Deddiekoel]

Ik ben tegen een probleem aangelopen dat ik eigenlijk niet had verwacht. Het gaat om een klasse waarmee ik van twee tekst bestanden een tree moeten creeren en in die tree elke node van een mooi x en y coordinaat moet voorzien.

Ik ga als volgt te werk. Eerst lees ik de twee input bestanden in een aparte vector. Vector 1 (uit bestand 1) bevat een lijst met begin nodes de tweede vector bevat een lijst met parent child relaties. Om de tree te kunnen creeren maak ik gebruik van een DOM Document object. Hier maak ik eerst een algemene root aan en voeg daarna voor elk object uit de eerste vector een child toe. Elke node bestaat uit een algemene tag name ("Node" in dit geval) met 3 attributen: id, x, y. De naam van de node zoals deze in de vector staat vul ik in bij het id attribuut en de x en y attributen laat ik leeg. Als ik deze start nodes heb ingevuld ga beginnen met het creeren van mijn boom aan de hand van de waarden in de tweede vector. Hiervoor heb ik een loop die per node de kinderen ophaalt van zichzelf en zijn siblings en zo steeds alles afgaat totdat er gen kinderen meer zijn. Hiervoor moet hij wel steeds voor elke node door de tweede vector loopen. Wat ik wel doe is als ik een of meerdere child nodes heb gevonden dan verwijderen ik deze uit de vector (met Vector.remove(index) methode). De tweede vector wordt dus steeds kleiner.
Als ik de tree heb gemaakt dan ga ik door de tree heen lopen om zo structureel alle nodes van een x en y coordinaat te voorzien. Ik doe dit nadat de tree klaar is omdat ik bij het toewijzen van achter naar voren werk (ik begin bij een leaf) omdat dit voor mij de duidelijkste weergave geeft.

Uiteindelijk moet ik een bestand genereren waarin de naam van elke node staat met daarachter de x en de y waarde. Hiervoor gebruik ik de Document.getElementByTagName("Node") waarbij alle nodes (hebeen immers allemaal de tag naam "Node") in een NodeList krijg en deze kan ik zo wegschrijven in een bestand.

Dit alles werkt op zich allemaal prima. Maar als ik wat grotere bestanden gebruik dan raakt Java heel sneller zonder geheugen. Pas met een -Xmx256m toevoeging krijg ik de melding niet meer. Het probleem is dan dat de verwerking dan heeeeeeel lang diuurt. Dit is het geval als ik 10000 startnodes heb (1e vector) en 20000 parent-child verwijzingen (2e vector).

Ik vraag me nu af waar dit aan kan liggen? Het inlezen van de bestanden is geen probleem. Deze zijn respectievelijk 1,65 Mb (waarin elke waarde 6x voorkomt, dus 60000 regels voor de utieindelijke 10000 nodes) en 891 kb voor de 20000 regels met parent-child verwijzingen.

Dan zou het natuurlijk kunnen dat mijn keuze voor de DOM structuur niet goed is. Het voordeel voor mij is dat ik zo makkelijk de parent-child-sibling structuur heb waarmee ik mijn tree kan bouwen en mijn coordinaten kan toewijzen. Maar de tree bevat uiteindelijk 20000 nodes en dat zou toch nog wel te doen moeten zijn. But please correct me if I'm wrong.

Wat voor mij dan nog zou het probleem zou kunnen zijn is het continue doorzoeken van de vector met 20000 elementen dit gebeurt precies 10000 keer. Maar die vector van 20000 zou dis steeds kleiner moeten worden.

Kortom ik weet niet waar de geheugen problemen vandaan komen en als ik java genoeg geheugen geef waarom hij zo vreselijk traag is. Is er een betere manier om dit alles aan te pakken?

Voor de volledigheid is hier mijn code:

code:

/*
 * Created on Dec 6, 2004
 */
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.Vector;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;
import javax.xml.transform.Result;
import javax.xml.transform.Source;
import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.dom.DOMSource;
import javax.xml.transform.stream.StreamResult;

import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
/**
 * @author Coert van den Thillart
 */
public class GenerateSNOTree {

 static Document document; 
 int x = 0;
 int y = 1;
 int xcoord = 400;
 int ycoord = 300;
 FileOperator fo = new FileOperator();
 
 public GenerateTree(String xc, String yc, String inputPath, String outputPath, boolean debug){
  xcoord = Integer.parseInt(xc);
  ycoord = Integer.parseInt(yc);        
  Vector supply = getSupplyNodes(inputPath+"\\supply.txt");
  if(supply==null) terminate("Fatal Error:\tSupply file not found.");
  System.out.println("Extracted "+supply.size()+" supply nodes!");
  Vector arcList = getArcNodes(inputPath+"\\arc.txt");
  if(arcList==null) terminate("Fatal Error:\tSupply file not found.");
  System.out.println("Extracted "+arcList.size()+" arc nodes!");
  Vector output = new Vector(0);
 
   DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
 
   try {
    DocumentBuilder builder = factory.newDocumentBuilder();
   document = builder.newDocument();
   Element root = (Element) document.createElement("Root");
   document.appendChild(root);
   Vector nodeList = new Vector(0);
   Vector nodeLists = new Vector(0);
   for(int telSupp=0; telSupp<supply.size(); telSupp++){
    String supplyData = (String) supply.get(telSupp);
    Element supplyEl = (Element) document.createElement("Node");
    supplyEl.setAttribute("id", supplyData);
    supplyEl.setAttribute("x", "");
    supplyEl.setAttribute("y", ""); 
    root.appendChild(supplyEl);
    nodeList.add((Node) supplyEl);
   }
   nodeLists.add(nodeList);
   boolean lastLeaf=false;
   while(lastLeaf==false){
    Vector childrenLists = new Vector(0);
    //Iterate through nodeLists vector
    for(int telNls=0; telNls<nodeLists.size(); telNls++){
     Vector childrenList = new Vector(0);
     Vector children = new Vector(0);
     nodeList = (Vector) nodeLists.get(telNls);
 
     //Iterate through nodeList to start parsing the nodes
     for(int telNl=0; telNl<nodeList.size(); telNl++){
      Node parent = (Node) nodeList.get(telNl);
      String nodeId = 
      parent.getAttributes().getNamedItem("id").getNodeValue();
      children = getChildNodes(arcList, nodeId, true);
      if(children.size()==0){
       if(childrenList.size()==0) continue;
       else {
        childrenLists.add(childrenList.clone());
        continue;
       }
      }
      else{
       for(int telChild=0; telChild<children.size(); telChild++){
        String childName = children.get(telChild).toString();
        //Element child = (Element) 
        document.createElement(getNodeType(childName));
        Element child = (Element) 
        document.createElement("Node");
        child.setAttribute("id", childName);
        child.setAttribute("x", "");
        child.setAttribute("y", "");                                
        parent.appendChild(child);
        childrenList.add(child);
       }
       childrenLists.add(childrenList.clone());
      }
     }
    }
    if(childrenLists.size()>0) 
    nodeLists = (Vector) childrenLists.clone();
    else lastLeaf=true;
   }
  } 
  catch (ParserConfigurationException pce) {
      // Parser with specified options can't be built
      pce.printStackTrace();
  }
  
  document = assignXY(document);        
  
  if(debug) writeXmlFile(document, outputPath+"\\SNO_Output.xml");
  fo.writeCharFile(createOutput(document, "\t"), outputPath+"\\tmp_newnodexy");
  System.out.println("Tab-delimited outputfile written "+outputPath+"\\tmp_newnodexy");
  if(debug) {
   fo.writeCharFile(createOutput(document, ","), outputPath+"\\output.csv");
   System.out.println("Comma-delimited outputfile written: "+outputPath+"\\output.csv");
  }
  // Enable this function to generate orphan report
  if(debug) writeOrphanReport(arcList, outputPath+"\\Arc_left.txt");
 }
 
 private Vector getSupplyNodes(String filePath){
  File sourceFile = new File(filePath);
  if(!sourceFile.isFile()) return null;
  Vector output = new Vector(0);
  String record = new String();
  String lastLine = new String();
  try{
   FileReader src = new FileReader(sourceFile);
   BufferedReader source = new BufferedReader(src);
   while((record=source.readLine())!=null){
    String[] line = record.split("\t");
    for(int tel=0; tel<line.length; tel++) 
    line[tel] = line[tel].replaceAll("\"", "");
    String strippedLine = line[0];
    if(!strippedLine.equals(lastLine)){
     lastLine = strippedLine;
     if(line.length>0) output.add(strippedLine);
    }
   }
  }
  catch(Exception e){
   e.printStackTrace();
  }
  return output;
 }
 
 private Vector getArcNodes(String filePath){
  File sourceFile = new File(filePath);
  if(!sourceFile.isFile()) return null;
  Vector output = new Vector(0);
  String record = new String();
  String[] lastLine = new String[3];
  try{
   FileReader src = new FileReader(sourceFile);
   BufferedReader source = new BufferedReader(src);
   while((record=source.readLine())!=null){
    String[] line = record.split("\t");
    for(int tel=0; tel<line.length; tel++) 
    line[tel] = line[tel].replaceAll("\"", "");
    String[] strippedLine = {line[1], line[2]};
    if(!strippedLine[0].equals(lastLine[0]) 
    || !strippedLine[1].equals(lastLine[1])){
     lastLine = strippedLine;
     if(line.length>0) output.add(strippedLine);
    }
   }
  }
  catch(Exception e){
   e.printStackTrace();
  }
  return output;
 }
    
 private static void writeXmlFile(Document doc, String filePath) {
  try {
   // Prepare the DOM document for writing
   Source source = new DOMSource(doc);

   // Prepare the output file
   File destFile = new File(filePath);
   if(!destFile.isDirectory()) destFile.mkdirs();
   if(destFile.exists())destFile.delete();
   destFile.createNewFile();
   Result result = new StreamResult(destFile);
   // Write the DOM document to the file
   Transformer xformer = 
   TransformerFactory.newInstance().newTransformer();
   xformer.transform(source, result);
   System.out.println("XML generated at: "+filePath);
  } 
  catch (Exception e) {
      e.printStackTrace();
  } 
 }
 private Vector getChildNodes(Vector arcList, String parentNode, boolean removeFound){
  Vector children = new Vector(0);
  Vector found = new Vector(0);
  for(int telArc = 0; telArc<arcList.size(); telArc++){
   String[] arcLine = (String[]) arcList.get(telArc);
   if(arcLine[0].equals(parentNode) 
   && (arcLine[1].substring(0,2).equalsIgnoreCase("st") 
    || arcLine[1].substring(0,2).equalsIgnoreCase("pr") 
    || arcLine[1].substring(0,2).equalsIgnoreCase("sd"))) {
    found.add(""+telArc);
    children.add(arcLine[1]);
   }
  }
  if(removeFound && found.size()>0){
   for(int telFnd=found.size()-1; telFnd>=0; telFnd--){
    String index = found.get(telFnd).toString();
    arcList.remove(Integer.parseInt(index));
   }
  }
  return children;
 }
 private String getNodeType(String name){
  String code = name.substring(0,2);
  if(code.equalsIgnoreCase("st")) return "Storage";
  else if(code.equalsIgnoreCase("pr")) return "Process";
  else if(code.equalsIgnoreCase("sd")) return "Storage_Demand";
  else return code;
 }
 private void writeOrphanReport(Vector v, String outputpath){
  FileOperator fo = new FileOperator();
  StringBuffer input = new StringBuffer();
  for(int telV=0; telV<v.size(); telV++){
   String[] line = (String[]) v.get(telV);          
   for(int tStr=0; tStr<line.length; tStr++) 
   input.append(line[tStr]).append("\t\t");

   String type = getNodeType(line[0]);
   NodeList searchNodes = document.getElementsByTagName(type);
   boolean found=false;
   for(int tn = 0; tn<searchNodes.getLength(); tn++){
    if(searchNodes.item(tn).getAttributes().getNamedItem("id").getNodeValue().equals(line[0])) found=true;
   }
   if(found)input.append("\t\t").append("X");
   else input.append("\t\t").append("-");
   input.append("\r\n");
  }
  fo.writeCharFile(input.toString(), outputpath);
  System.out.println("Orphan report generated at: "+outputpath);
 }
 private Node getLeaf(Node start){
  Node leaf = start;
  boolean leafFound = true;
  while(leafFound){
   NodeList childNodes = start.getChildNodes();
   if(childNodes.getLength()==0) {
    leaf = start;
       leafFound = true;
    break;
   }
   else {
    x++;
    start = childNodes.item(0);
   }
  }
  return leaf;
 }
 private Document assignXY(Document doc){
  Node start = doc.getFirstChild();
  boolean lastLeaf = false;
  while(!lastLeaf){
   Node leaf = getLeaf(start);
   leaf.getAttributes().getNamedItem("x").setNodeValue(""+(x*xcoord));
   leaf.getAttributes().getNamedItem("y").setNodeValue(""+(y*ycoord));
   assignEmptyParents(leaf);
   Node sibling = leaf.getNextSibling();
   if(sibling==null){
    Node parent = leaf.getParentNode();
    if(parent==null || !parent.hasAttributes()) lastLeaf=true;
    else{
     x--;
     while(parent.getNextSibling()==null) {
      parent = parent.getParentNode();
      if(parent==null || !parent.hasAttributes()) {
       lastLeaf=true;
       break;
      }
      else x--;
     }
     if(!lastLeaf) {
      start = parent.getNextSibling();
      y++;
     }
    }
   }
   else {
    y++;
    start = sibling;
   }
  }
  return doc;
 }
 private void assignEmptyParents(Node leaf){
  boolean notdone=true;
  int xstart = x;
  while(notdone){
   Node parent = leaf.getParentNode();
   if(parent!=null && parent.hasAttributes()){
    x--;
    if(parent.getAttributes().getNamedItem("x").getNodeValue()=="" 
    && parent.getAttributes().getNamedItem("y").getNodeValue()==""){
     parent.getAttributes().getNamedItem("x").setNodeValue(""+(x*xcoord));
     parent.getAttributes().getNamedItem("y").setNodeValue(""+(y*ycoord));
     leaf = parent;
    }
    else notdone = false;
   }
   else notdone = false;
  }
  x = xstart;
 }
 private String createOutput(Document doc, String delim){
  StringBuffer output = new StringBuffer();
  NodeList nodes = doc.getElementsByTagName("Node");
  for(int nTel=0; nTel<nodes.getLength(); nTel++){
   Node n = nodes.item(nTel);
   if(output.indexOf(n.getAttributes().getNamedItem("id").getNodeValue())==-1){
    output.append("\""+n.getAttributes().getNamedItem("id").getNodeValue()+"\"").append(delim);
    output.append(n.getAttributes().getNamedItem("x").getNodeValue()).append(delim);
    output.append(n.getAttributes().getNamedItem("y").getNodeValue()).append("\r\n");
   }
  }
  return output.toString();
 }
 private void terminate(String error){
  System.out.println(error);
  System.exit(1);
 }
}

[ Voor 42% gewijzigd door Deddiekoel op 16-12-2004 12:31 ]

[Alarmnummer]

Kan je er voor zorgen dat je tekst niet zo breed is? Het is erg vervelend om voor iedere regel te gaan scrollen.

[Deddiekoel]

Sure...done...not quite...dit lijkt er al wat meer op...

[ Voor 125% gewijzigd door Deddiekoel op 16-12-2004 11:50 ]

[MSalters]

DOM is een XML I/O methodiek, geen datastructuur voor intern gebruik!

[Zoijar]

Removen uit het midden van een vector, zou wel eens een vector relocatie kunnen veroorzaken. Je gaat dus 10000 keer een vector van begginende grootte 20000 kopieren. Gemiddeld zijn dat dan zo'n 100 miljoen relocaties...dat is traag en vreet geheugen. Denk dat het hem daar in zit?

(plus uiteraard wat msalters al zei...)

[ Voor 9% gewijzigd door Zoijar op 16-12-2004 11:57 ]

[Eskimootje]

Alarmnummer schreef op donderdag 16 december 2004 @ 11:37:
Kan je er voor zorgen dat je tekst niet zo breed is? Het is erg vervelend om voor iedere regel te gaan scrollen.

Klik eens boven de code naast de tekst "code:" op het pijltje

[Deddiekoel]

Zoijar schreef op donderdag 16 december 2004 @ 11:56:
Removen uit het midden van een vector, zou wel eens een vector relocatie kunnen veroorzaken. Je gaat dus 10000 keer een vector van begginende grootte 20000 kopieren. Gemiddeld zijn dat dan zo'n 100 miljoen relocaties...dat is traag en vreet geheugen. Denk dat het hem daar in zit?

(plus uiteraard wat msalters al zei...)

Hmmm, dus ik zou dat verwijderen niet moeten doen? Of op een andere manier?

[Zoijar]

Een linked list gebruiken Als je niet verwijdert wordt het iets van een O(n²) operatie, dan kan je nog beter je 2e vector doorlopen en de plek in de boom zoeken, dat is O(n log n). Met verwijderen is het...hmmm...weet ik even niet zeker. ook iets van n log n, denk ik?

(ik moet nu weg, geen tijd om echt na te denken maar zou daar in ieder geval eens naar kijken...weet niet of efficientere algorithmes betsaan voor tree building...wie weet, google misschien)

[ Voor 26% gewijzigd door Zoijar op 16-12-2004 12:05 ]

[Deddiekoel]

Het probleem met het doorlopen van de 2e vector en de gevonden zaken refereren aan de boom is dat de volgorde in het bestand niet logisch is. Regel 1 kan dus refereren aan een parent node die pas in regel 20000 wordt gecreeerd.

Wat ik ook niet begrijp is dat als ik niet verwijder (is momenteel een flag) dan raakt het progje in een loop. Maar ik snap niet waarom...
Edit: Gevonden waarom hij gaat loopen, heel slordig vautje. Ik checkte ergens of een children array null was maar ik moest kijken of de size() nul was... Aangepast in code...

Ik zal wel eens gaan bekijken wat een linked list is.

[ Voor 38% gewijzigd door Deddiekoel op 16-12-2004 12:30 ]

[ronaldmathies]

Mischien is dit een interesant artikel voor je http://www.onjava.com/pub...1/05/30/optimization.html

Dit gaat over performance van ArrayList, Vector en LinkedList.

Er staan ook allerlei tests in die hun beweringen onderbouwen inclusief tabellen met statistieken.

Hun Conclusie:

The measurements and the other factors we've considered clearly indicate that ArrayLists and Vectors usually provides better performance than LinkedLists and synchronized wrapped LinkedLists. Even in cases where you might have thought that the LinkedList would provide better performance, you may be able to coax superior performance from ArrayList by altering how elements are added, for example by reversing the collection order.

There are situations where LinkedLists will provide better performance; with, for example, very large collections where many elements need to be added to both the beginning and end of the collection. But in general, I recommend using ArrayList/Vector as the default and using LinkedList only where there is an identified performance problem in which a LinkedList improves the performance.

[Alarmnummer]

Ik heb je verhaal niet echt doorgenomen (te weinig tijd), maar als je veel moet gaan zoeken door die lijsten, dan is een lijst misschien niet de handigste optie omdat je gemiddeld n/2 elementen bij langs moet. Ik gebruik dan heel vaak een map (hashmap/hashtable) om snel te kunnen zoeken. Hierdoor krijg je een constante zoektijd. Als de volgorde van die elementen ook belangrijk is (waarschijnlijk wel) dan kun je ook kijken naar LinkedHashMap.

[Deddiekoel]

Ik heb dus net dat rare loop probleem opgelost en nu werkt alles opeens goed!
Binnen een minuut heb ik mijn tree, ook in XML formaat. Alleen het maken van het output bestand (30000 regels) duurt even (kleine 2 minuten).

Maar ik ga toch naar die hashtables kijken, want wellicht dat er bij nog grotere bestanden wel problemen ontstaan en die kan ik misschien hiermee aanpakken.

Edit:
Wat ik alleen niet snap is dat de output van de XML tree in een XML formaat wel snel is. Is het mogelijk om via de XSLT transformer ook een plat ouput bestand te maken?

[ Voor 20% gewijzigd door Deddiekoel op 16-12-2004 12:50 ]

[Deddiekoel]

Ik heb wat nieuwe testdata gegenereerd en daarop loopt hij weer vast...

Het gaat nu om 250000 supply nodes en 500000 andere (import bestanden zijn 44 en 24 Mb groot). Ik heb de JVM allereerst al 256 Mb Extended memory moeten geven om hem uberhaubt te laten lopen. Hij is echter nu al 2 uur bezig en ik zie nog steeds geen resultaat. Terwijl hij voor de 10000 supply nodes in 35 sec erdoorheen was.

Hoewel deze orde van grote niet echt reeel is zou ik toch graag willen weten hoe ik een dergelijk volume kan aanpakken. Ik wil nu eerst gaan beginnen met het bekijken van de mogelijkheden van hashmaps. Maar ik vraag me ook af hoe ik:
- Makkelijker de inhoud van die bestanden kan verwerken (is met name voor de 2e vector lastig omdat de volgorde volledig random is)
- Sneller de output kan gegeneren (hier is het probleem dat ik geen nodes twee keer wil wegschrijven, dus moet er een soort van check in...)

[Deddiekoel]

Alarmnummer schreef op donderdag 16 december 2004 @ 12:41:
Ik heb je verhaal niet echt doorgenomen (te weinig tijd), maar als je veel moet gaan zoeken door die lijsten, dan is een lijst misschien niet de handigste optie omdat je gemiddeld n/2 elementen bij langs moet. Ik gebruik dan heel vaak een map (hashmap/hashtable) om snel te kunnen zoeken. Hierdoor krijg je een constante zoektijd. Als de volgorde van die elementen ook belangrijk is (waarschijnlijk wel) dan kun je ook kijken naar LinkedHashMap.

Ik heb een beetje naar hashtables gekeken maar ik zie niet hoe ik daarmee sneller kan zoeken. Om waarden eruit te kunnen halen zal ik dan echt met een for loop aan de gang moeten...

[Macros]

Voor je links en nodes zou ik echte objecten maken. Als dan je nodes en links uniek zijn, dan moet je een hashcode en equals functie voor ze schrijven. Dan kan je echte datastructuren gebruiken zoals HashMap en HashSet.
Daar kan je VEEEEEEL efficenter in zoeken dan in een Vector (lees: trage ArrayList).

[Alarmnummer]

Deddiekoel schreef op vrijdag 17 december 2004 @ 13:38:
[...]


Ik heb een beetje naar hashtables gekeken maar ik zie niet hoe ik daarmee sneller kan zoeken. Om waarden eruit te kunnen halen zal ik dan echt met een for loop aan de gang moeten...

Als jij kan werken met een key (bv een of andere id), dan kan jij daar 'ranzig' snel elementen in opzoeken. Zoeken in een map heeft een constante tijd en zoeken in een lijst heeft een zoektijd die lineair toeneemt met het aantal elementen ni die lijst. Dus hoe groter die lijst, hoe langzamer het zoeken gaat. En dat probleem heb je met een map dus niet.

[nnomiS]

Je zou rood/zwart bomen kunnen gebruiken voor je implementatie. Zijn binaire bomen met een paar extra regels zodat ze altijd redelijk gebalanceerd zijn en je er in O(nlogn) alle operaties op kan uitvoeren. De HasMap en set van java maken intern ook gebruik van die data structuren. Ik zou dus proberen het m.b.v. een HasMap te implementeren. (Zelf een rood/zwart boom maken is opzich redelijk lastig).

[momania]

Tip: [google=java,binarySearch,HashTable,site:sun.com]

Lees goed hoe het hele collection framework werkt en welke collection je objecten waarvoor het beste kan gebruiken.
Vector is sowieso vaak al niet nodig. Enige dat een vector biedt is synchonization en traagheid

Je moet het idd meer hebben van de HashTables, LinkedHashMaps etc... en dan vooral proberen om de Collections.binarySearch te benutten als je in grote collections moet zoeken

[Deddiekoel]

Zijn hashtables ook sneller als ik erdoorheen moet loopen met een for-loop?

Het probleem is nl. dat ik niet echt met een unieke key kan werken. Elke node kan meerdere childs hebben en meerdere parents. Dus als ik een hashtable gebruiken dan moet ik nog steeds zoeken op een bepaalde waarde. Nu kennen hashtables wel een "containsValue" methode maar daar heb ik niets aangezien deze alleen maar aangeeft of die waarde er in zit... Als ik nl. snel een key bij een waarde kan vinden dan split ik mijn links vector wel op in twee vectoren waarvan de keys hetzelfde zijn...

Maar als het zoeken door hashtable mbv van een for-loop en de get methode sneller is dan moet ik die natuurlijk gaan implementeren!

[Alarmnummer]

Deddiekoel schreef op zaterdag 18 december 2004 @ 11:41:
Zijn hashtables ook sneller als ik erdoorheen moet loopen met een for-loop?

Nope... heel traag dus dat wil je echt niet.

Kijk.. de vraag voor het gebruik van een map is dat jij een key kunt maken. Is dat mogelijk? Dan kan je iets heel snel opzoeken in een map (het lijkt me verstandig dat je (ooit) je gaat verdiepen in hashtables ed.. extreem belangrijk). Als jij geen key kunt maken (soms is dat niet mogelijk) dan moet je kijken naar een alternatieve structuur.

[edit]
Moppelt iets in de geest van.. position object... mogelijk key kandidaat...

Node node = nodeMap.get(new Position(1244,1334));

Nu heb jij ranzigsnel jouw node gevonden op basis van een bepaalde positie.

Ik heb je verhaal eerlijk gezegd niet goed doorgenomen (te veel tekst) dus ik weet niet of dit de oplossing is.

[ Voor 67% gewijzigd door Alarmnummer op 18-12-2004 11:53 ]

[Deddiekoel]

Ik denk niet dat ik een key kan bepalen. Het probleem is dat ik voor een bepaalde node de children wil zoeken. Dus hetgeen dat echt perfect zou zijn voor de key is iets dat niet uniek is.

Waar ik nu aan zit te denken is om de key wel uniek te maken. Bij het genereren van de lijst met parent-child relaties kan ik steeds kijken of een parent al bestaat. Als dit het geval is kan ik de nieuwe parent voorzien van een extensie. Ondertussen hou ik een global counter bij die het aantal "kopieen" telt. Als ik moet gaan zoeken hoef ik alleen maar het aantal zoekacties te doen als die counter aangeeft (dat is immers het grootst aantal duplicaten dat ik heb...
Wat ik me dan nog afvraag is of het dan zin heeft om de gevonden nodes te verwijderen...

[Alarmnummer]

Deddiekoel schreef op zaterdag 18 december 2004 @ 12:08:
Ik denk niet dat ik een key kan bepalen. Het probleem is dat ik voor een bepaalde node de children wil zoeken. Dus hetgeen dat echt perfect zou zijn voor de key is iets dat niet uniek is.

Een positie is toch altijd uniek?

[Deddiekoel]

Alarmnummer schreef op zondag 19 december 2004 @ 08:48:
[...]

Een positie is toch altijd uniek?

Ik heb nog niet naar Position objects gekeken, maar van wat ik afleidt uit je voorbeeld moet ik al een tree hebben. Maar in de tree zoek ik eigenlijk niet meer. Het zoeken gebeurt bij het maken van de tree...

Om mijn verhaal even samen te vatten. Ik maak van twee bestanden (een met startpunten en een met de relaties tussen twee nodes (parent-child)) een tree en loop daarna door die tree heen om er een x en y coordinaat aan te hangen... Daarna genereer ik een outputbestanden met daarin alle nodes (geen duplicaten) met hun x en y coordinaat.

[Alarmnummer]

Hmmm tja... of je zult je probleem helder (en extreem kort) moet uitleggen of zelf nog maar even proberen want met deze informatie kan ik je geen beter antwoord geven.

[ Voor 14% gewijzigd door Alarmnummer op 19-12-2004 15:25 ]

[Verwijderd]

Deddiekoel schreef op zondag 19 december 2004 @ 15:16:
[...]
Om mijn verhaal even samen te vatten. Ik maak van twee bestanden (een met startpunten en een met de relaties tussen twee nodes (parent-child)) een tree en loop daarna door die tree heen om er een x en y coordinaat aan te hangen... Daarna genereer ik een outputbestanden met daarin alle nodes (geen duplicaten) met hun x en y coordinaat.

Als je een tree gebruikt als datastructuur en je wilt erin zoeken, dan is het verstandig om te weten waarop je moet zoeken. Als dit de id is, dan is het een 'gemakkelijk' probleem. Als je wilt zoeken op de x, y coordinaten, dan wordt het wat lastiger.
In het geval van de id, dan kan je een binaire gebalanceerde boom maken als elke parent-child relatie maximaal 1:2 is. Als dat niet het geval is, dan zal je een ander soort tree moeten zoeken. Hiervoor zijn al behoorlijk wat datastructuren beschikbaar en er is veel daarover op google te vinden.
Als je wilt zoeken op coordinaten, dan is het verstandig om je eerst even in te lezen in geometrische datastructuren / algoritmen. Bijvoorbeeld een Kd-tree of range trees. Dit zijn echter lastigere structuren en ik weet niet of je dit wel nodig hebt.

In ieder geval zal je duidelijker moeten zijn wat je precies wilt, want ik snap het ook niet geheel. Wat is bijvoorbeeld het doel van het maken van deze datastructuur en de output genereren en het zoeken.

[Verwijderd]

Kan je datstructuur 2 niet wat strikter ordenen dan?
Je schrijft namelijk dat je iedere keer vector 2 opnieuw moet doorlopen.

Hoe zijn die (parent-/child-)relaties gedefinieerd? Met zowel de mogelijkheid tot parent- als child-relaties?
In dat geval zou het beter zijn om alleen de child-relaties in datastructuur 2 op te slaan.
Dan kan je een bottum-up-algoritme toepassen. Als je datastructuur dan wat striker ordent (bijv. door paal en perk te stellen via het formaat van het bestand waarin datastructuur 2 wordt bijgehouden), dan hoef je vector 2 niet telkens opnieuw te doorlopen.

Jij bent nu aan het zoeken, zoals je zelf al schrijft, maar kan je niet een formaat voor datastructuur 2 (in bestand 2) als het volgende aanhouden:

XML:

<relatie nodeid="0">
    <child>
        <node id="2"/>
        <node id="5"/>
        <node id="24234"/>
    </child>
</relatie>
<relatie nodeid="1">
    <child>
        <node id="3"/>
        <node id="4"/>
        <node id="7"/>
    </child>
</relatie>

En voor iedere node dus sequentieel de bijbehorende relaties bijhouden? Dan hoef je niet meer opnieuw te zoeken, je kunt het proces gewoon lineair doorlopen.

[Deddiekoel]

Mijn god wat zijn hashtables snel. Het zijn eigenlijk gewoon associative arrays (die ik ken uit PHP).

Maar ik heb hetgeen ik boven heb uitgedacht ook geimplementeerd en de resultaten zijn schokkend! Voor 250000 supply nodes en 500000 relaties heeft hij nu 16 sec nodig. Iets waarik een paar dagen terug na uren wachten maar mee ben gestopt. Een andere test met 100000 supply nodes deed er 4 uur over!

Maar er blijft nog een groot probleem en dat is de creatie van het output bestand. Zoals gezegd gebruik ik een DOM tree om de boomstructuur te maken. Als ik dit DOM Document naar een bestand wegschrijf is dit binnen een seconde klaar. Maar als ik dezelfde data via een StringBuffer probeer weg te schrijven naar een bestand doet hij daar echt uren over (in verhouding iig).

Wat ik doe is het volgende. In mijn DOM Tree heten alle nodes "Node". Middels de getElementByName("Node") methode krijg ik zo een NodeList met alle nodes die ik wil wegschrijven. Wat ik nu doe is door de NodeList lopen en ze 1 voor 1 toevoegen aan een StringBuffer en deze StringBuffer uiteindelijk als String wegschrijven. Hier zit een extra handelijk op. Voordat ik een node aan de StringBuffer toevoeg kijk ik eerst of de naam van die node al in de Stringbuffer voorkomt (middels de indexOf() methode). Als dat het geval is dan schrijf ik hem niet weg....

Maar dit is dus niet echt bijster snel. Zijn er betere alternatieven hiervoor? Het output bestand moet de alleen op elke regel de 3 attributen (id, x, y) van elke node wegschrijven en elke node mag er maar 1 keer in staan.

[Alarmnummer]

Deddiekoel schreef op maandag 20 december 2004 @ 14:58:
Mijn god wat zijn hashtables snel. Het zijn eigenlijk gewoon associative arrays (die ik ken uit PHP).

Maar ik heb hetgeen ik boven heb uitgedacht ook geimplementeerd en de resultaten zijn schokkend! Voor 250000 supply nodes en 500000 relaties heeft hij nu 16 sec nodig. Iets waarik een paar dagen terug na uren wachten maar mee ben gestopt. Een andere test met 100000 supply nodes deed er 4 uur over!

Mooi zo

Wat ik doe is het volgende. In mijn DOM Tree heten alle nodes "Node". Middels de getElementByName("Node") methode krijg ik zo een NodeList met alle nodes die ik wil wegschrijven. Wat ik nu doe is door de NodeList lopen en ze 1 voor 1 toevoegen aan een StringBuffer en deze StringBuffer uiteindelijk als String wegschrijven. Hier zit een extra handelijk op. Voordat ik een node aan de StringBuffer toevoeg kijk ik eerst of de naam van die node al in de Stringbuffer voorkomt (middels de indexOf() methode). Als dat het geval is dan schrijf ik hem niet weg....

Hoe werkt een indexOf? Kijk de code van java eens door.. zie wat er gebeurt en je weet ook exact wat de oorzaak van je probleem is.

Jij hebt nu weer het probleem van onnodig lang zoeken (string.indexOf) geintroduceerd. Je kan het wederom bij houden in een Map. Datastructuren zijn niet gratis.. ze hebben allemaal hun sterke en zwakke punten. Zorg dat je dus het java collection framework (in ieder geval Set,Map en List) goed begrijpt.

[ Voor 15% gewijzigd door Alarmnummer op 20-12-2004 15:37 ]

[Stephan Oudmaijer]

gewoon sax gebruiken ipv dom. zal je geheugen probleem iig oplossen.

[Alarmnummer]

CK schreef op maandag 20 december 2004 @ 15:32:
gewoon sax gebruiken ipv dom. zal je geheugen probleem iig oplossen.

Lees zijn laatste bericht nog even goed door en kijk welke toegevoegde waarde sax heeft voor zijn probleem. Zijn probleem ligt bij de check op dubbel wegschrijven en het daarbij behorende scannen door een string. Het heeft dus niets te maken met Sax aangezien het geen XML probleem is.

[Deddiekoel]

Alarmnummer schreef op maandag 20 december 2004 @ 15:28:
Hoe werkt een indexOf? Kijk de code van java eens door.. zie wat er gebeurt en je weet ook exact wat de oorzaak van je probleem is.

Jij hebt nu weer het probleem van onnodig lang zoeken (string.indexOf) geintroduceerd. Je kan het wederom bij houden in een Map. Datastructuren zijn niet gratis.. ze hebben allemaal hun sterke en zwakke punten. Zorg dat je dus het java collection framework (in ieder geval Set,Map en List) goed begrijpt.

Ik heb het zoeken in de frameBuffer vervangen met alweer een Hashtable. Wat ik nu doe is elke element dat ik wegschrijf ook wegschrijven in een nieuwe Hashtable. Als een weg te schrijven element al bestaat schrijf ik niets weg anders wel. Maar dit levert echter een marginale snelheidswinst op.

Maar het moet haast wel sneller kunnen aangezien het wegschrijven van het DOM document naar een XML bestand echt een paar seconden duurt (11 sec voor 750000 nodes). Ik wil nu dus gaan kijken of ik via XSLT niet mijn gewenste bestand kan krijgen. Alleen weet ik niets van XSLT...is het mogelijk om daarmee de door mij vereiste check uit te voeren?

[Alarmnummer]

Deddiekoel schreef op maandag 20 december 2004 @ 16:08:
[...]

Ik heb het zoeken in de frameBuffer vervangen met alweer een Hashtable. Wat ik nu doe is elke element dat ik wegschrijf ook wegschrijven in een nieuwe Hashtable. Als een weg te schrijven element al bestaat schrijf ik niets weg anders wel. Maar dit levert echter een marginale snelheidswinst op.

2 dingen:
1) is je boom nu niet verneukt omdat je niet alle elementen wegschrijft?
2) kijk ook even naar de identityhashmap. In principe is die hetzelfde als een normale hashmap, maar ipv dat een 'dure' equals operatie wordt uitgevoerd werkt hij op basis van object identiteit (dus ==) Dit zal trouwens nog maar een marginele snelheids winst opleveren denk ik.

Maar het moet haast wel sneller kunnen aangezien het wegschrijven van het DOM document naar een XML bestand echt een paar seconden duurt (11 sec voor 750000 nodes). Ik wil nu dus gaan kijken of ik via XSLT niet mijn gewenste bestand kan krijgen. Alleen weet ik niets van XSLT...is het mogelijk om daarmee de door mij vereiste check uit te voeren?

Los problemen niet op door complexiteit te introduceren, maar door simpliciteit te introduceren.

Dit soort oplossingen valt onder de noemer: prutsen, knoeien, broddelen, hacken. Het kan misschien even wel.. maar op lange termijn gaat het je enorm opbreken.

[ Voor 7% gewijzigd door Alarmnummer op 20-12-2004 16:26 ]

[Deddiekoel]

Ok, dan gooien we het even over een andere boeg. Wat is de snelste manier om een bestand weg te schrijven...

[Rey Nemaattori]

Deddiekoel schreef op vrijdag 17 december 2004 @ 13:03:
Ik heb wat nieuwe testdata gegenereerd en daarop loopt hij weer vast...

Het gaat nu om 250000 supply nodes en 500000 andere (import bestanden zijn 44 en 24 Mb groot). Ik heb de JVM allereerst al 256 Mb Extended memory moeten geven om hem uberhaubt te laten lopen. Hij is echter nu al 2 uur bezig en ik zie nog steeds geen resultaat. Terwijl hij voor de 10000 supply nodes in 35 sec erdoorheen was.

Het loopt kwadratisch of zelfs exponentieel toe. Dubbel zo veel nodes == 4x zo lang of
nodes⁴