Как я могу быстро сказать, содержит ли список список?

StackOverflow https://stackoverflow.com/questions/4192961

Вопрос

Есть несколько связанных вопросов, но я ищу решение, специфичное для моего случая. Существует массив (обычно) 14 целых чисел, каждый из которых в диапазоне от 1 до 34. Как я могу быстро сказать, появляется ли каждый INT в конкретном статическом списке, по крайней мере, один раз в этом массиве?

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

if (array.Count < 13) {
    return;
}

var required = new int[] {
    0*9 + 1,
    0*9 + 9,
    1*9 + 1,
    1*9 + 9,
    2*9 + 1,
    2*9 + 9,                
    3*9 + 1,
    3*9 + 2,
    3*9 + 3,
    3*9 + 4,
    3*9 + 5,
    3*9 + 6,
    3*9 + 7,
};

IsThirteenOrphans = !required.Except (array).Any ();

Требуемый список не является динамичным, то есть он всегда будет одинаковым во время выполнения. Использование LINQ не является обязательным, основным аспектом является производительность.

Редактировать:

  • Входной массив не отсортирован.
  • Входные значения могут появляться несколько раз.
  • Входной массив будет содержать не менее 14 элементов, то есть 1 больше, чем требуемый массив.
  • Есть только 1 требуемый массив, и он статичен.
  • Значения в требуемых различны.
  • Вы можете предположить, что гистограмма дешевая для создания.

Обновлять: Я также заинтересован в решении для отсортированного входного массива.

Это было полезно?

Решение

Идея 1
Если вам нужно сравнить с несколькими required Списки тогда вы можете отсортировать список ввода, а затем просто сравнить его, итерация. Но сортировка, конечно, не слишком быстрая, но не слишком медленная. Но если вы сравните с несколькими необходимыми списками, накладные расходы сортировки могут быть быстро амортизированы.

Как только массив сортируется, сравнивать, тривиально:

for(int i = 0; i < 14; i++)
  if(arr[i] != required[i]) return false;

return true;

Идея 2
Или если 14 целых чисел отличаются/уникальны, вы можете просто сделать required хешст и сделать

input.Count(i => required.Contains(i)) == 14

Но я не знаю, не тестируя его, если это быстрее, чем сортировка.

Идея 3
Рассчитайте быстрый хэш, который инвариантен в результате перестановки по 14 INT, и сравните его с известным значением require. Анкет Только если хэш -совпадения сделают более дорогое сравнение.

//Prepare/precalculated
int[] hashes = new int[34];
Random random = new Random();
for(int i = 0; i < 34; i++)
  hashes[i] = random.NextInt();

//On each list
int HashInts(int[] ints)
{
  int result = 0;
  foreach(int i in ints)
    result += hashes[i - 1];

  return result;
}

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

Идея 4
Создать гистограмму:

int[] CreateHistogram(int[] ints)
{
  int[] counts = new int[34];
  foreach(int i in ints)
  {
    counts[i - 1]++;
  }

  return counts;
}

Вы можете избежать создания массива, повторно используя существующий массив, если производительность В самом деле важный.

Другие советы

Если у вас доступен интегральный тип 34+ и операции битов в стиле C, то вы можете вычислить такое целое число V из списка переменных (если список v [0], v [1], ... Тогда V (1 << v [0]) | (1 << v [1]) ... где 1 имеет тот же тип, что и v) и имеет предопределенное такое целое число для статического списка, вычисленного аналогично. Тест, чтобы увидеть, содержится ли статический список в списке переменных, затем (s & ~ v) == 0.

Одна возможность состоит в том, чтобы изменить способ, которым вы храните данные. Поскольку диапазон возможных значений ограничен 1-34, вместо того, чтобы хранить список чисел, вы можете сохранить подсчет каждого присутствующего номера:

int[] counts = new int[34];

Если в вашем списке есть один 1 и два 3s, то считается [0] == 1 && counts [2] = 2 (вы можете альтернативно использовать 1 индексацию, если это делает вещи быстрее (меньше вычитаний.))

Теперь, чтобы оценить, что каждый int в списке появляется хотя бы один раз, вы просто индексируете в массиве последовательно для каждого x и проверяете, что все значения [x]> 0 Список формы, но это только проблема, если вам также часто нужно просматривать данные в форме списка. Еще одно преимущество в этом формате хранения заключается в том, что добавление/удаление в подсчет никогда не будет включать в себя более одного элемента массива; В форме списка удаление элемента в середине списка влечет за собой копию нескольких элементов.

Если вы хотите быстрый путь, вам не следует использовать LINQ, если все элементы списка все более реше 35, вы можете удалить if (lst[i] < 35)Список Traverse Travers counting sort:

public bool FindExactMatch(int[] array, List<int> lst)
{
    bool[] a34 = new bool[35];

    foreach(var item in array)
    {
        a34[item] = true;
    }

    int exact = 0;

    for (int i = 0; i < lst.Count; i++)
    {
        if (a34[lst[i]])
        {
            exact++;
            if (exact == array.Length) return true;

            a34[lst[i]] = false;
        }
    }

    return false;
}

для отсортированного списка, если размер списка большой, вы можете сделать lst.BinarySearch(array[i]) Что требует 14 * * log (n) * c1 больше всего, и я думаю, что это также достаточно эффективно, если вы реализуете, это может стать быстрее, и я не проверял бинарный поиск с моей собственной реализацией, но min, max, сортируйте в Linq медленнее, чем (от 4 до 10 раз) ваша собственная (хорошая) реализация. И если разоренный размер списка маленький, я предпочитаю использовать алгоритм, как выше, потому что постоянный c1 небольшой в вышеупомянутом алгоритме и может быть больше в алгоритме бинарного поиска.

Это выглядит как хороший кандидат на поединок, поскольку необходимые значения отличаются, статичны, и между 1 и 34. Вместо того, чтобы сохранить, требуемые в качестве массива, сохраняют его как постоянный. В ваших массивах, чтобы проверить, создайте новый Ulong, заполненный левым сдвигом, каждое значение и побитовое или.

const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34);

public static bool ContainsDistinct13Values(int[] array)
{
    ulong word = 0;
    foreach (int i in array)
    {
        word |= (1UL << i);
    }
    return word == comparator;
}

Редактировать:Поэтому я понял ваш вопрос и, вероятно, имею хорошее чрезмерное решение. Еще один вопрос: насколько хороша производительность.

static void Main(string[] args)
{
    var required = new int[]
                       {
                           0*9 + 1,
                           0*9 + 9,
                           1*9 + 1,
                           1*9 + 9,
                           2*9 + 1,
                           2*9 + 9,
                           3*9 + 1,
                           3*9 + 2,
                           3*9 + 3,
                           3*9 + 4,
                           3*9 + 5,
                           3*9 + 6,
                           3*9 + 7,
                       };

    precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset);

    for (int i = 0; i < required.Length; i++)
    {
        precomputedResult |= (UInt16)(1 << i);
    }

    int[] array = new int[34]; // your array goes here..
    Console.WriteLine(ContainsList(array));

    Console.ReadKey();
}

// precompute dictionary
private static Dictionary<int, UInt16> precomputed;
// precomputed result
private static UInt16 precomputedResult = 0;

public static bool ContainsList(int[] values)
{
    UInt16 result = 0;
    for (int i = 0; i < values.Length; i++)
    {
        UInt16 v;
        if (precomputed.TryGetValue(values[i], out v))
            result |= v;
    }

    return result == precomputedResult;
}

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

bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;
    }

    if (notContains == false) break;
}

Это намного быстрее, чем ваш подход. Проверьте приведенный ниже код с добавленным таймером. Ваш подход занял 5 мс, но новый занимает 0 мс.

System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch();
aTimer.Start();

var IsThirteenOrphans = !required.Except(array).Any();
aTimer.Stop();

System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch();
bTimer.Start();
bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;            
    }

    if (notContains == false) break;
}

bTimer.Stop();
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top