Самый быстрый способ поместить количество элементов массива между пределами

Question

Например ...

1. У меня есть массив целых чисел, который инициализируется случайными значениями от 1 до 1000
2. Массив имеет 1M элементов (вероятно, он будет иметь гораздо больше, но это только пример)
3. Количество вхождений каждого элемента должно быть от 10 до 1010

Какой самый быстрый способ настройки элементов этого массива, чтобы они соответствовали упомянутым критериям?

Мое первое решение просто слишком медленное, если максимальное число вхождений близко к массиву. Длина (1M) / valuesSpan (1000)

Я пробовал что-то вроде (Это только для выравнивания макс.случаев, решение для нижнего предела почти такое же):

Int64[] DistinctArrayElements = distinctArrayElements;
Dictionary<Int64, Int32> occurrences = new Dictionary<Int64, Int32>();

foreach (Int64 DistinctElement in DistinctArrayElements)
{
    occurrences.Add(DistinctElement, 0);
}

foreach (Int64 ArrayElement in Arr)
{
    occurrences[ArrayElement] += 1;
}
//I know this initialization can be done more nicely, so don't bother with this.

for (int j = 0; j < Arr.Length; j++)
{
    if (occurrences[Arr[j]] > upperNoOfOccurrences)
    {
        for (int i = 0; i < Arr.Length; i++)        
        {
            if (occurrences[Arr[i]] < upperNoOfOccurrences)
            {
                Arr[j] = Arr[i];
                occurrences[Arr[i]] += 1;
                occurrences[Arr[j]] -= 1;
            }
        }
    }
}

Answer 1

Я бы отсортировал ваш словарь так, чтобы числа, которые появляются меньше, были первыми. Таким образом, вам не нужно каждый раз искать подходящее число, просто замените его на меньшее. Вот псевдокод, чтобы объяснить это:

struct dict {
    key, value
}

linkedList<dict> occurrences;

initialize occurrences
sort it (smallest values first)

// start from the one with greatest number of occurrences
n = occurrences.last;

// keep going until occurrences of n is greater than upperNoOfOccurrences
while n.value.value > upperNoOfOccurrences and didn't reach first element
    repeat = true

    do:
        // required occurrences to subtract to be within the limit
        required = upperNoOfOccurrences - n.value.value

        // maximum occurrences we can add to the first
        maxAllowed = upperNoOfOccurrences - occurrences.first.value.value

        // if we can do that
        if required < maxAllowed:
            occurrences.first.value.value += required
            n.value.value -= required
            repeat = false
        else:    // n.value.value is still greater than upperNoOfOccurrences
            occurrences.first.value.value += maxAllowed 
            n.value.value -= maxAllowed 
            repeat = true
        end if

        // keep occurrences sorted
        newPos = occurrences.first.next
        while occurrences.first.value > newPos.value.value:
            newPos = newPos.next

        move occurrences.first before newPos
    while repeat
end while

now rebuild your array with occurrences. it will
be sorted  but it doesn't matter does it? ;)

Answer 2

Вот простой и точный метод, который равномерно выбирает наборы чисел, которые соответствуют вашим критериям.

1. Пусть M = количество различных значений; N = количество элементов массива; L = нижний предел на количество экземпляров каждого значения; U = верхний предел на счет; D = U-L. Например, M = 1000, N = 1000000, L = 10, U = 1010 и D = 1000.
2. Создать массив S размером M * D. Установите первые N записей S в 1, а остальные в ноль.
3. Shuffle S через shuffle Фишера-Йейтса. (См. Ссылки здесь )
4. Создать массив T размером M.
5. Для i до M установите T [i] = L + S [i D] + S [i D + 1] + ... + S [i * D + D -1].
6. Создать массив V размером N. Заполните его T [0] экземплярами 0-го значения и т. Д., т.е. - T [i] экземплярами i '-го значения. , за каждый i. Поскольку S содержит N 1, V будет заполнен полностью и точно.
7. Shuffle V через shuffle Фишера-Йейтса. Тогда массив V удовлетворяет исходным критериям.

Обратите внимание, что шаги 2-5 - это O (M D), в то время как 6-7 - это O (N + M), причем последние настолько хороши, насколько это возможно, и первые, вероятно, аналогично, так как M D - это O (N) в вашей постановке задачи.

Answer 3

Я не совсем понимаю, что ты хочешь делать. Тем не менее, кажется, что обрабатывать массив много раз - пустая трата времени. Вы все могли бы сделать только один цикл (и немного заглядывать вперед, когда у вас заканчиваются «свободные» уникальные значения). Следующее, конечно, не самый хороший код, который я написал, но я думаю, что это решение вашей проблемы.

HashSet<long> forbidden = new HashSet<long>(); // maximum size of 1000, contains values that exceeded the limit
Queue<long> remaining = new Queue<long>(1000); // stores found unique values within the limit in a queue, that will be used if we bounce into the limit
Dictionary<long, int> frequencies = new Dictionary<long, int>(1000);
int lastPeekIndex = 0;
for (int i = 0; i < Arr.Length; i++) {
  if (!frequencies.ContainsKey(Arr[i])) {
    frequencies[Arr[i]] = 0;
    remaining.Add(Arr[i]);
  }

  if (frequencies[Arr[i]] == upperLimit) {
    if (!forbidden.Contains(Arr[i])) forbidden.Add(Arr[i]);
    var next = Int64.MinValue;
    try {
      next = remaining.Dequeue();
      while (forbidden.Contains(next)) next = remaining.Dequeue();
    } catch (InvalidOperationException) { // Arrr! we have not yet observed enough unique values
      for (int j = Math.Max(i, lastPeekIndex) + 1; j < Arr.Length; j++)
        if (!frequencies.ContainsKey(Arr[j])) {
          frequencies[Arr[j]] = 0;
          next = Arr[j];
          lastPeekIndex = j;
        }
    }
    Arr[i] = next;
    frequencies[next]++;
    if (frequencies[next] < upperLimit) remaining.Enqueue(next);
  } else frequencies[Arr[i]]++;
}

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