C # Более быстрый способ фильтрации цикла с массивом int в качестве индекса?

Question

Извините, если это дубликат, первый вопрос здесь ...

Я хочу оперировать большим массивом структур, называемых заметками.Но я не хочу оперировать каждым элементом заметок.Я пытаюсь использовать filter массива int (int[]), чтобы пропустить немало его, как показано в приведенном ниже коде.

Note[] notes = new Note[]
{ 
   // Struct stuff ... 
};

int[] filter = new int[]{ 4,20,50,367... };

for (int i = 0; i < notes.Length; i++)
{
     bool flag = false;
     for (int j = 0; j < filter.Length; j++)
     {
          if (i == filter[j])
          {
               flag = true;
               break;
          }
      }

      if (flag) continue;
      // Do something on notes[i]
}

Проблема в том, что код будет работать очень медленно (я думаю), когда расширяется и массив примечаний, и массив фильтров.Итак, есть ли лучший и более быстрый способ сделать это?Обратите внимание, что размер фильтра может быть любым в зависимости от других условий

Answer 1

Мы можем избавиться от внутреннего цикла с помощью HashSet<int>, имея при этом O(|filter| + |notes|) сложность времени вместо начальной O(|filter| * |notes|):

Note[] notes = new Note[] { 
  ... //Struct stuff 
};

int[] filter = new int[] { 
  4, 20, 50, 367... 
};

HashSet<int> toExclude = new HashSet<int>(filter);

for (int i = 0; i < notes.Length; i++) {
  if (toExclude.Contains(i)) // O(1) time complexity 
    continue;

  //Do something on notes[i] 
}

Answer 2

Вы можете отфильтровать заметки, используя Linq, следующим образом:

Note[] notes = new Note[]{ ...//Struct stuff };
int[] filter = new int[]{ 4,20,50,367... };

var filteredNotes = notes.ToList().Where(note => !filter.Contains(note.Id)).ToList();

foreach(var note in filteredNotes)
{
//Do something on note
}

Однако вам нужно будет проверить производительность, так как Linq имеет тенденцию работать медленно в определенных обстоятельствах.

Answer 3

Вы можете зациклить массив фильтров и создать новый логический массив, содержащий все элементы, которые вы хотите пропустить как истинные.

bool[] filterArray= new bool[notes.Length];
foreach(var index in filter)
{
   if(index<filterArray.Length)
       filterArray[index]=true;
}

Тогда вам нужно просто проверить индекс этого массива.

for (int i = 0; i < notes.Length; i++)
{
     if(!filterArray[i]){
     //Do something on notes[i]
     }

}

Сложность этого кода будет O(m+n*X), где m - длина массива фильтра, n длина массива узлов и X сложность вашей операции на notes[i]. Предполагая mO (n * X).

Ваша сложность сейчас O(m*n*X)