Оптимизация алгоритма линейного поиска

Question

Я только что закончил домашнюю проблему для Computer Science 1 (да, это домашнее задание, но выслушайте меня!). Теперь задание выполнено на 100% и работает, поэтому мне не нужна помощь. Мой вопрос включает в себя эффективность алгоритма, который я использую (мы пока не оцениваем алгоритмическую эффективность, мне просто очень интересно).

Функция, которую я собираюсь представить, в настоящее время использует модифицированную версию алгоритма линейного поиска (который я придумал сам по себе!), Чтобы проверить, сколько номеров в данном лотерейном билете соответствует выигрышным номерам , считая, что оба числа в билете и набранные числа находятся в порядке возрастания. Мне было интересно, есть ли способ сделать этот алгоритм более эффективным?

/* 
* Function: ticketCheck 
* 
* @param struct ticket 
* @param array winningNums[6] 
* 
* Takes in a ticket, counts how many numbers 
* in the ticket match, and returns the number 
* of matches. 
* 
* Uses a modified linear search algorithm, 
* in which the index of the successor to the 
* last matched number is used as the index of 
* the first number tested for the next ticket value. 
* 
* @return int numMatches 
*/ 
int ticketCheck(struct ticket ticket, int winningNums[6]) 
{ 
    int numMatches = 0; 
    int offset = 0; 
    int i; 
    int j; 

    for(i = 0; i < 6; i++) 
    { 
     for(j = 0 + offset; j < 6; j++) 
     { 
      if(ticket.ticketNum[i] == winningNums[j]) 
      { 
       numMatches++; 
       offset = j + 1; 
       break; 
      } 
      if(ticket.ticketNum[i] < winningNums[j]) 
      { 
       i++; 
       j--; 
       continue; 
      } 
     } 
    } 

    return numMatches; 
} 

Answer 1

Это более или менее, но не совсем. В большинстве ситуаций это O (n), но это O (n^2), если каждый ticketNum больше, чем каждый выигрышныйNum. (Это происходит потому, что внутренний j петля не break когда j==6, как и должно быть, но выполняет следующий i итерации вместо этого.)

Вы хотите, чтобы ваш алгоритм для увеличения либо i или j на каждом шагу, и прекращается при i==6 или j==6. [. Ваш алгоритм почти удовлетворяет этому, как указано выше] В результате, требуется только один цикл:

for (i=0,j=0; i<6 && j<6; /* no increment step here */) { 
    if (ticketNum[i] == winningNum[j]) { 
     numMatches++; 
     i++; 
     j++; 
    } 
    else if (ticketNum[i] < winningNum[j]) { 
     /* ticketNum[i] won't match any winningNum, discard it */ 
     i++; 
    } 
    else { /* ticketNum[i] > winningNum[j] */ 
     /* discard winningNum[j] similarly */ 
     j++; 
    } 
} 

Очевидно, что это O (п); на каждом этапе он либо увеличивает i, либо j, поэтому большинство шагов, которые он может сделать, это 2 * n-1. Это почти то же поведение, что и ваш алгоритм, но легче следовать и легче видеть, что это правильно.

Answer 2

Вы в основном ищете размер пересечения двух наборов. Учитывая, что большинство лотосов используют около 50 шаров (или так), вы можете сохранить числа как биты, которые установлены в unsigned long long. Обнаружение общих чисел - это простой вопрос: Идентификация этих двух вместе: commonNums = TicketNums & winningNums;.

Поиск размера пересечения - это вопрос подсчета одного бита в полученном числе, объект, который был covered previously (хотя в этом случае вы должны использовать 64-разрядные номера или пару 32-разрядных числа, а не одно 32-разрядное число).

Answer 3

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

PS: Не забывайте, что общие результаты по эффективности имеют больше смысла, если принять количество шаров или размер билета, чтобы быть переменным. В противном случае он слишком сильно зависит от машины.

Answer 4

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

int NumsArray[MAX_NUMBER+1]; 
memset(NumsArray, 0, sizeof NumsArray); 

for(i = 0; i < 6; i++) 
    NumsArray[winningNums[i]] = 1; 

for(i = 0; i < 6; i++) 
    numMatches += NumsArray[ticket.ticketNum[i]]; 

12 петля раундов вместо до 36 Окружающий код в качестве упражнения.

EDIT: Он также имеет то преимущество, что не нужно сортировать оба набора значений.

Answer 5

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

Для многих лотерей будет достаточно 64 бит, поэтому uint64_t должен быть достаточно большим, чтобы покрыть это. Кроме того, некоторые архитектуры имеют инструкции для подсчета бит, установленных в регистре, которые некоторые компиляторы могут распознавать и оптимизировать.

Эффективность этого алгоритма основана как на диапазоне номеров лотереи (M), так и на количестве лотерейных номеров на билет (N). Параметр, если флаги являются O (N), в то время как одновременное использование двух битовых массивов и подсчет бит могут быть O (M), в зависимости от того, будет ли ваш M (диапазон номеров лото) больше размера, Целевой процессор может предварительно выполнить эти операции непосредственно. Скорее всего, хотя M будет небольшим, и его влияние, вероятно, будет меньше, чем влияние N на производительность.