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

Я только что закончил домашнюю работу для 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;
}

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

Ответ 2

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

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

Ответ 3

Да, есть что-то более быстрое, но, вероятно, использование большего объема памяти. Сделайте массив, полный 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: он также имеет то преимущество, что не нужно сортировать оба набора значений.

Ответ 4

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

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

Ответ 5

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

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

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