/хотите Список, Соответствующий Алгоритму

Хорошо, как насчет этого:

Есть гигантские "бассейны"

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

Что я имею в виду:

Пул A (Для тех, кто просит A)

- Раздел B (Для тех, кто просит A, у которых есть B)

- Раздел C (Для тех, кто просит A, у которых есть C, даже если у них есть B)

Пул B

- Раздел A

- Раздел B

Пул C

- Раздел A

- Раздел C

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

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

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

И, затем, возраст будет иметь приоритет, старые сделки будут выбираться, а не новые.

Конечно, вы всегда можете разделить систему на три категории; «Хочет», «Имеет» и «Открытые предложения». Итак, допустим, у User1 есть Item A, у User2 есть Item B и C, и он обменивает их на предмет A, но User1 по-прежнему хочет Item D, а User2 хочет Item E. Итак, User1 (при условии, что он является «владельцем» сделки) отправляет запрос, или хотите получить товар D и объект E, поэтому предложение остается в силе и попадает в список «Открытых предложений». Если он не будет принят или отредактирован в течение двух дней или около того, он автоматически аннулируется. Итак, User3 ищет Item F и Item G, а в «Списке есть» ищет элементы F и G, которые разделены между User1 и User2. Он понимает, что открытое предложение User1 и User2 включает в себя запросы на элементы D и E, которые у него есть. Поэтому он решает «присоединиться» к операции, и она принимается на их условиях, обменивая и обменивая предметы между собой.

Допустим, пользователю User1 теперь нужен элемент H. Он просто ищет элемент в списке «Have» и среди результатов обнаруживает, что User4 обменяет элемент H на элемент I, который, как оказалось, есть у User1. Торгуют, все хорошо.

Просто сделайте его только BC. Это решит все проблемы.

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

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

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

Это будет быстро. O (log n) для каждой операции вставки. В худшем случае O (n) для предложения торговых партнеров, но вы ограничиваете это временем обработки.

1. Вы уже ведете список элементов для каждого пользователя.
2. Дайте каждому пользователю оценку, равную сумме значений имеющихся у них предметов.
3. Вести список пользователей-HAVES и user-WANTS для каждого элемента (@Dialecticus), отсортированных по количеству пользователей. (Вы можете сортировать по запросу или сохранять динамическую сортировку списков каждый раз, когда пользователь меняет свой список HAVE.)
4. Когда пользователь user1 запрашивает предлагаемых торговых партнеров
   • Перебрать свои элементы элемент по значению.
   • Итерация по пользователю-HAVES user2 для каждого элемента в порядке оценки пользователя.
   • Вычислить стоимость сделки для пользователь1 торгует с пользователем2 .
   • Вспомните лучшую сделку на данный момент.
   • Сохранять обработанные хэши пользователей на данном этапе, чтобы избежать повторного вычисления значения для пользователя несколько раз.
   • Прекратить, когда у вас закончится время обработки (ваша гарантия в реальном времени).

Сортировка по значению элемента и оценке пользователя - это приближение, которое делает это быстро. Однако я не уверен, насколько это было бы неоптимально. Конечно, есть простые примеры, когда это не поможет найти лучшую сделку, если вы не завершите ее. На практике кажется, что этого может хватить.В пределе вы можете сделать его оптимальным, позволив ему работать, пока он не исчерпает списки на шагах 4.1 и 4.2. С перевернутыми списками связана дополнительная стоимость памяти, но вы не сказали, что у вас ограниченная память. И вообще, если вам нужна скорость, нередко приходится жертвовать пространством, чтобы получить ее.

Я отмечаю пункт по буквам, а пользователя по номеру.

• m - количество элементов во всех списках есть / хочу (есть или хотят, не имеют и хотят)
• x - количество пользователей.

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

1 - ABBCDE FFFGH
2 - CFGGH BE
3 - AEEGH BBDF

Для каждой пары пользователей вы генерируете два значения и где-то храните их, вы должны сгенерировать их только один раз, а затем актуализировать. Сортировка первой таблицы и создание второй составляют O (m * x * log (m / x)) + O (log (m)) и потребуют O (x ^ 2) дополнительная память. Это следующие значения: сколько получит первый пользователь и сколько еще (при желании вы можете изменить эти значения, умножив их на значение конкретного элемента).

1-2 : 1 - 3 (user 1 gets 1) - (user 2 gets 3)
1-3 : 3 - 2
2-3 : 1 - 1 

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

• Добавление / удаление элемента - O (m * log (m / x)) (Вы просматриваете список желаний / желаний пользователя и выполняете бинарный поиск по списку желаний / желаний каждого другого пользователя и актуализируете данные )
• Поиск наилучшего соединения - O (1) или O (x) (Зависит от того, верен ли результат, сохраненный в кеше, или его нужно обновить. Вы просматриваете пары пользователей и делаете все, что хотите, с данные, чтобы вернуть пользователю наилучшее соединение)

По m / x Я оцениваю количество элементов в списке желаний / желаний одного пользователя.

В этом алгоритме я предполагаю, что все данные не хранятся в базе данных (я не знаю, возможен ли двоичный поиск с базами данных) и что вставка / удаление элемента в список O (1) .

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