Что такое четырехъядерный связанный список?

Question

В настоящее время я работаю над реализацией структуры типа списка на работе, и мне нужно, чтобы она была безумно эффективной. В поисках эффективных структур данных я наткнулся на патент на список четырех квадратов, и это вызвало у меня интерес, настолько, что я забыл о своей текущей задаче и вместо этого начал исследовать список четырех. К сожалению, интернет очень скрытно относился ко всему, и Google мало что дал с точки зрения полезных результатов. Единственное объяснение, которое я получил, было описанием патента, в котором говорилось:

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

Это, к сожалению, только делает меня более озадаченным, так как я не могу обернуться вокруг объяснения непрофессионала. Поэтому я обращаюсь ко всем вам в надежде, что вы сможете объяснить мне, что же на самом деле представляет собой эта четырехъядерная история, поскольку я знаю, что не зная, довольно быстро приведет меня к стенам и стенам.

Знаете ли вы, что такое список с четырьмя ссылками?

Answer 1

Я не могу быть уверен, но это звучит немного как список пропусков .

Даже если это не так, вам может пригодиться пропуск списков. (Насколько мне известно, они однонаправлены, однако.)

Answer 2

Формально я раньше не сталкивался с этим термином, но из описания патента я могу сделать обоснованное предположение.

Связанный список - это список, в котором каждый узел имеет ссылку на следующий ...

a -->-- b -->-- c -->-- d -->-- null

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

  --<--   --<--   --<--  
|       |       |       |
a -->-- b -->-- c -->-- d -->-- null

Давайте предположим, что список отсортирован. Если я хочу выполнить бинарный поиск, я обычно иду в середине списка, чтобы найти средний узел, затем захожу в соответствующий интервал и повторяю. Однако обратный путь в связанном списке всегда O (n) - я должен перейти по всем ссылкам. Из описания я думаю, что они просто добавляют дополнительные ссылки от узла, чтобы «пропустить» фиксированное число узлов в списке впереди. Что-то вроде ...

  --<--   --<--   --<--  
|       |       |       |
a -->-- b -->-- c -->-- d -->-- null
|                       |
|----------->-----------|
 -----------<-----------

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

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

Answer 3

Я не знаю, является ли это «списком с четырьмя ссылками», но звучит примерно так:

struct Person {
    // Normal doubly-linked list.
    Customer *nextCustomer;
    Customer *prevCustomer;

    std::string firstName;

    Customer *nextByFirstName;
    Customer *prevByFirstName;

    std::string lastName;

    Customer *nextByLastName;
    Customer *prevByLastName;
};

То есть: вы поддерживаете несколько заказов в вашей коллекции. Вы можете легко перемещаться в порядке firstName или в порядке lastName. Поддерживать актуальность ссылок дорого, но навигация довольно быстрая.

Конечно, это может быть что-то совершенно другое.

Answer 4

Одним из источников патента является этот . Похоже, есть две претензии, вторая из которых более актуальна:

Реализованный на компьютере способ организации и поиска набора связанных записей, в котором каждая запись включает в себя:

i) поле фиксированного идентификатора; и

ii) поле идентификатора переменной; способ, содержащий этапы:

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

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

(c) генерирование первого и второго наборов указателей поля, при этом первый набор указателей поля включает в себя упорядоченный набор указателей, которые указывают на каждое N-е поле с фиксированным ID, когда записи упорядочены относительно поля с фиксированным ID, и второй набор указателей включает упорядоченный набор указателей, которые указывают на каждое N-е поле идентификатора переменной, когда записи упорядочены относительно поля идентификатора переменной;

(d) при поиске конкретной записи со ссылкой на ее поле с фиксированным идентификатором проводят двоичный поиск по первому набору указателей поля, чтобы определить начальный указатель и окончательный указатель, определяющий диапазон, в котором находится конкретная запись ;

(e) проверка с помощью линейного скарча фиксированных полей идентификатора в пределах диапазона, определенного на шаге (d) для определения местоположения конкретной записи;

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

(g) проверка путем линейного поиска полей идентификатора переменной в пределах диапазона, определенного на шаге (f), для поиска конкретной записи.

Когда вы работаете с патентом gobbledegook, я думаю, это означает примерно то же самое, что иметь два списка пропусков (один для прямого поиска, один для обратного поиска) для каждого из двух ключей (отсюда всего 4 списка и имя ' четырехъядерный список '). Я не думаю, что это очень хороший патент - он выглядит очевидным применением пропуска списков к набору данных, где у вас есть два ключа для поиска.

Answer 5

Насколько я понимаю, список, связанный с квадраторами, - это список, который можно просмотреть (назад или вперед) в O (n) двумя различными способами, то есть отсортировать по FieldX или FieldY:

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

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

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

Answer 6

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