Выполнение двух функций одновременно

Question

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

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

Моя реализация для линейного поиска

struct node* find(long int value) { 
    struct node*temp = head, *temp1 = tail;
    while(temp->id < value && temp1->id > value){
        temp = temp->next;
        temp1 = temp1->prev;
    }
    if(temp->id == value)
        return temp;
    else if(temp1->id == value)
        return temp1;
    else
        return NULL;
}

Здесь temp1 переходит назад, только после того, как темп переместился вперед

Мой вопрос:

Есть ли способ двигаться как вперед (темп), так и назад(temp1) указатели одновременно?

[Я имею в виду перемещение обоих указателей параллельно, чтобы даже уменьшить время совместного восприятия]

КЛЮЧЕВЫЕ СЛОВА: отсортированный двусвязный список, язык C

Answer 1

Если ваша реализация C поддерживает это, вы можете включить заголовок <threads.h> и создать новые потоки. Это позволит вам использовать один поток для сканирования списка вперед, а другой - для сканирования списка назад. Тем не менее, есть ряд проблем с этим, в том числе:

• Если у вас так много узлов, чтобы проверить, что создание дополнительного потока для их сканирования значительно сокращает время выполнения, тогда у вас так много узлов, что вы могли бы улучшить их поиск, используя лучшую структуру, чем двусвязный список, такие как деревья или хеширование.
• Довольно легко начать новую тему, но сложнее остановить ее разумным способом. Вам нужно будет остановить один поток, когда другой найдет результат, и вам нужно будет остановить оба потока, когда они встретятся друг с другом в списке. Это означает добавление дополнительного кода для связи и координации.
• Создание нескольких потоков может, при правильных обстоятельствах, сократить время выполнения «настенных часов» (как долго, пока вы не получите результат), но это не уменьшает потребляемые ресурсы. Вместо того чтобы использовать один процессор в течение некоторого времени, вы будете использовать два процессора в течение примерно одного общего времени. («Всего» означает сумму времени выполнения на каждом процессоре.)
• Некоторые из используемых процессорами ресурсов являются общими. Например, они оба обращаются к одной и той же основной памяти. В зависимости от того, какие именно ресурсы требуются вашей программе, использование большего количества процессоров может не помочь. Если узким местом в вашей программе является чтение данных из памяти, первый процессор все равно просто ожидает в памяти, а добавление второго процессора будет означать, что они оба ждут. Это может быть хорошо в системе, где вы являетесь единственным пользователем и не используете его интенсивно (хотя есть вопросы о том, сколько энергии можно использовать, делая это так или иначе). Однако в системе, где запущено много процессов и требуется полная мощность процессора, использование нескольких процессов может быть расточительным, чтобы быстрее получить результат.
• И наоборот, современные процессоры очень сложны и включают внутреннюю многопроцессорность - процессор может сравнивать некоторые данные одновременно с запросом на загрузку других данных из памяти. Иногда умное написание кода может использовать преимущества этой многопроцессорной обработки для одновременного выполнения нескольких задач. Например, вы могли бы написать код, который поочередно работает вперед в списке и обратно, каждый шаг за раз вместе в одном цикле, и процессор может выполнить это эффективно, сравнивая данные из одного направления при загрузке данных для другого направления.

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

Answer 2

Язык C не поддерживает одновременное выполнение нескольких функций. Единственное решение - многопоточность. Это, однако, может открыть окно Пандоры (как одна функция может знать, где работает другая функция?), Которая решается с помощью критических секций, мьютексов, ... Это интересная тема, но вы можете много читать перед заставить что-то работать.