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

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 больше, чем каждый winnerNum. (Это потому, что внутренний цикл 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. Это поведение почти такое же, как у вашего алгоритма, но его легче отслеживать и легче увидеть, что оно правильное.

Answer 2

Вы в основном ищете размер пересечения двух сетов. Принимая во внимание, что большинство лотосов используют около 50 шаров (или около того), вы можете хранить числа в виде битов, которые установлены в длинном без знака. Нахождение общих чисел является простым делом И для того, чтобы соединить их вместе: commonNums = TicketNums & winningNums;.

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

Answer 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 Окружающий код оставлен в качестве упражнения.

РЕДАКТИРОВАТЬ: он также имеет преимущество в том, что нет необходимости сортировать оба набора значений.

Answer 4

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

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

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

Answer 5

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

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