проблема с производительностью

Question

ОК, поэтому мне нужно знать, может ли кто-нибудь увидеть способ уменьшить количество итераций этих циклов, потому что я не могу. Первый цикл while - это переход через файл, чтение одной строки за раз. Первый цикл foreach затем сравнивает каждый из compareSet с тем, что было прочитано в первом цикле while. Затем следующий цикл while связан с подсчетом бит.

В соответствии с просьбой об объяснениях моего алгоритма:

Там есть файл, который слишком велик, чтобы поместиться в памяти. В нем содержится слово, за которым следуют страницы в очень большом документе, в котором написано это слово. EG:

sky 1 7 9 32 ....... (это не в этом формате, но вы получаете идею).

поэтому parseLine читает в строке и преобразует его в список int, который похож на бит-массив, где 1 означает, что слово находится на странице, а 0 означает, что это не так.

CompareSet - это куча других слов. Я не могу вместить весь свой список слов в память, поэтому я могу подобрать только их подмножество. Это куча слов, как пример «неба». Затем я сравниваю каждое слово в compareSet с Sky, видя, находятся ли они на одной странице.

Итак, если небо и другое слово имеют 1 набор с определенным индексом в битовом массиве (имитируемый как массив int для производительности), они находятся на одной странице. Таким образом, алгоритм учитывает события любых двух слов на конкретной странице. В итоге у меня будет список:

(для всех слов в списке) на той же странице, что и для всех слов в списке x раз.

Например, небо и земля находятся на одной странице x раз.

while ((line = parseLine(s)) != null) { 
    getPageList(line.Item2, compareWord); 
    foreach (Tuple<int, uint[], List<Tuple<int, int>>> word in compareSet) { 
     unchecked { 
      for (int i = 0; i < 327395; i++) { 
       if (word.Item2[i] == 0 || compareWord[i] == 0) 
        continue; 
       uint combinedNumber = word.Item2[i] & compareWord[i]; 
       while (combinedNumber != 0) { 
        actual++; 
        combinedNumber = combinedNumber & (combinedNumber - 1); 
       } 
      } 
     } 

Answer 1

Как мой старый профессор Bud говорил: «Когда вы видите, вложенные циклы, как это, ваши Spidey чувство должно быть идут CRAZY»

У вас есть какое-то время с вложенным в другое время. Это вложение циклов является экспоненциальным увеличением порядка операций. В вашем случае для цикла есть итерации 327395. Предполагая, что они имеют такое же или число итераций, это означает, что у вас есть порядок операций по

327,395 * 327,395 * 327,395 = 35,092,646,987,154,875 (insane) 

Это не удивительно, что все будет замедляться. Вам нужно переопределить алгоритм, чтобы удалить эти вложенные петли или объединить работу где-нибудь. Даже если числа меньше моих предположений, вложенность циклов создает много операций, которые, вероятно, не нужны.

Answer 2

Как уже упоминал Джоаль, никто не может оптимизировать этот алгоритм цикла. Но то, что вы можете сделать, это попытаться лучше объяснить, что вы пытаетесь выполнить, и каковы ваши жесткие требования. Возможно, вы можете использовать другой подход, используя некоторые, например, HashSet<T>.IntersectWith() или BloomFilter или что-то в этом роде.

Итак, если вам действительно нужна помощь, вы должны не только публиковать код, который не работает, но и то, что вам нужно выполнить в общей задаче. Возможно, у кого-то есть совершенно другая идея, чтобы решить вашу проблему, сделав весь ваш алгоритм устаревшим.