RAM ή CPU επηρεάζουν περισσότερο την ταχύτητα εκτέλεσης ενός προγράμματος;

[albNik]

Mια τελευταία προσπάθεια.

Εχεις μια λιστα απο 140 HashSet<string> των 20  και μια με 340000  List<string> των 20.

H HashSet.IntersectsWith() είναι optimized να βρίσκει τα κοινά στοιχεία πολύ γρήγορα (2 εικοσάδες είναι τίποτα).

Θα κάνεις 140*340000= 47εκ ελέγχους αντί για 19 δισ.

Έβαλα random words και το παρακάτω τρέχει σε 1.4 sec στο pc μου συμπεριλαμβάνοντας το χρόνο για να κατασκευάσω τις 2 λιστες. 

Το τελευταίο double loop που είναι ο έλεγχος για 5 κοινά κάνει μόνο 0.18 sec. 

var list_140 = new List<HashSet<string>>();
var list_340k = new List<List<string>>();

Random r = new Random();
for(int i = 0; i < 340000; i++)
{
    var list = new List<string>();
    for(int j = 0; j < 20; j++)
    {
        list.Add(r.Next(1, 1000).ToString());
    }
    list_340k.Add(list);
}

for(int i = 0; i < 140; i++)
{
    var list = new List<string>();
    for(int j = 0; j < 20; j++)
    {
        list.Add(r.Next(1, 1000).ToString());
    }
    list_140.Add(list.ToHashSet());
}

foreach(var hash in list_140)
    foreach(var sentence in list_340k)
    {
        hash.IntersectWith(sentence);
        if(hash.Count >= 5)
        {
            Console.WriteLine("found 5");
            // found 5 commons
        }
    }

 

Επεξ/σία 19 Ιουνίου 2022 από albNik

[Επισκέπτης]

Αυτό που περιγράφεις δεν μου δουλεύει. Παραθέτω ενδεικτικά τον κώδικα που χρησιμοποιώ

List<HashSet<string>> refListHash = new List<HashSet<string>>();	// η λίστα με τα 140 items.
while (διάβασε από την database) {
   words = το αντίστοιχο field απο την db
   // οι λέξεις είναι σε ένα πεδίο χωρισμένες με κόμμα οπότε τις σπάω σε διαφορετικές για να τις φορτώσω στο hash
   string[] separators = new string[] { "," };
   string[] wordsArray = words.Split(separators, StringSplitOptions.None);
   HashSet<string> tmpHashSet = new HashSet<string>(wordsArray);
	
   refListHash.Add(tmpHashSet);
}

List<HashSet<string>> corpusListHash = new List<HashSet<string>>();	// η λίστα με τα 340k items.
// η ίδια λογική με προηγουμένως

// οπότε στο τέλος έχω δύο Loops
foreach (var sourceWords in refListHash) {
   foreach (var targetWords in corpusListHash) {
      sourceWords.IntersectWith(targetWords);
      if (sourceWords.Count > 5) {
         // δεν μπαίνει ποτέ εδώ
      }
   }
}

Δεν βρίσκει ποτέ matches. Όλες οι λέξεις είναι ελληνικές, αν παίζει κανένα ρόλο. Το πρόγραμμα κάνει 3 δευτερόλεπτα να τρέξει, μαζί με τα reads από την db. Από αυτή την άποψη είναι εντυπωσιακοί οι χρόνοι.

Επεξ/σία 19 Ιουνίου 2022 από random_dude

[albNik]

Βασικα εχω ενα bug. Δεν ειναι θεμα ελληνικά/αγγλικά, τα string είναι unicode.

H sourceWords.IntersectWith(targetWords);  μεταβάλει την sourceWords (αφαιρει οσα δεν ειναι κοινα) και γινεται ολο και μικρότερη μεχρι που αδειαζει και δεν εχει κοινο τιποτα.

Φτιάξε μια sourceWordsCopy και κανε σε αυτην InterSectWith.  Ο χρόνος θα ειναι μεγαλύτερος τωρα.

var sourceWordsCopy=new HashSet(sourceWords);
sourceWordsCopy.IntersectWith(targetWords);
      if (sourceWordsCopy.Count > 5) {
         //
      });

 

Επεξ/σία 19 Ιουνίου 2022 από albNik

[Επισκέπτης]

Το έκανα και αυτό, αλλά και πάλι δεν δουλεύει.

foreach (var sourceWords in refListHash) {
   List<string> sourceWordsList = sourceWords.ToList();
   HashSet<string> tmpHashSet = new HashSet<string>(sourceWordsList.ToArray());

   foreach (var targetWords in corpusListHash) {
      tmpHashSet.IntersectWith(targetWords);
      if (tmpHashSet.Count > 5) {
                        
      }
   }
}

 

[albNik]

9 λεπτά πριν, random_dude είπε

Το έκανα και αυτό, αλλά και πάλι δεν δουλεύει.

foreach (var sourceWords in refListHash) {
   List<string> sourceWordsList = sourceWords.ToList();
   HashSet<string> tmpHashSet = new HashSet<string>(sourceWordsList.ToArray());

   foreach (var targetWords in corpusListHash) {
      tmpHashSet.IntersectWith(targetWords);
      if (tmpHashSet.Count > 5) {
                        
      }
   }
}

 

Χρειαζεται μεσα στο nested loop, πρεπει να δημιουργείς καινούριο πριν απο καθε IntersectWith, διαφορετικά αδειάζει και το tmpHashSet.

var tmpHashSet = new HashSet<string>(sourceWordsList);

 

Επεξ/σία 19 Ιουνίου 2022 από albNik

[Επισκέπτης]

ΟΚ, δουλεύει. 94 δευτερόλεπτα και με Parallel.ForEach στο εσωτερικό loop πέφτει στα 25 δευτερόλεπτα. Τέλεια. Το ένα δέκατο του αρχικού χρόνου.

 

[albNik]

Αν χρειαστείς περαιτέρω size/speed το παρακάτω είναι 10-12 sec χωρίς Parallel.For.

Xρησιμοποιώ το wordIndicesMap που πόσταρα σε προηγούμενο μήνυμα οπου τροποποίησα λίγο το loop για να φιλτράρω πεντάδες.

foreach(var sentence in list140_20)
{
    var commonIndices = new List<int>();
    foreach(var word in sentence)
    {
        if(wordIndicesMap.ContainsKey(word))
            commonIndices.AddRange(wordIndicesMap[word]);
    }
    var commonFive = commonIndices.GroupBy(x => x).Where(x => x.Count() >= 5).Select(x => x.Key).ToList();
    foreach(var ind in commonFive)
    {
        //sentence has 5 common words with list340000_20[ind]
    }
}

 

[Aris_]

το πρόγραμμα που φτιάχνεις δεν έχει multiple branches που το αποτέλεσμα τους θα άλλαζε την ροη θα προκαλούσε pipeline stalls-memory flush, ένας καλός compiler μπορεί να προβλέψει μεγάλο μέρος της ροής που έχεις και να τροφοδοτεί την cpu

αυτά από hardware σκοπιά 

σε linux υπάρχουν πιο εύκολα εργαλεία να σου λένε το ipc που έχεις σε real time με τον κώδικα που τρέχεις