Алгоритм для слияния наборов та доля по крайней мере 2 элемента
Вопреки распространенному мнению, вы можете фактически хранить состояние на клиенте, достаточно надежно для многих целей. Это то, что фреймворки, такие как Rails, делают по умолчанию, весь пользовательский сеанс (все данные сеанса) сохраняется в cookie, если не указано иное. Это не так просто, и это не то, что вы должны когда-либо реализовывать сами.
Также верно, что все, что находится на клиенте, полностью контролируется потенциально злонамеренным пользователем. Ну, если нет надлежащих средств защиты.
Ключом к этому является аутентификация сообщения и / или шифрование (обратите внимание, что последнее не обязательно подразумевает первое, это разные вещи).
Вы можете мысленно смоделировать такие вещи, как сервер отправляет себе сообщение (состояние сеанса, которое он не хочет запоминать между двумя запросами), и сервер хочет убедиться, что сообщение (1) не изменилось во время передача через клиента (аутентификация сообщения) и (2) в случае необходимости держится в секрете (шифрование).
Чтобы это работало, у отправителя и получателя должен быть общий секрет. Поскольку отправитель и получатель в этом случае совпадают (сервер), это означает, что для вашего приложения должен быть сохранен секрет. Например, в Rails это происходит от SECRET_KEY_BASE. После этого все, что отправлено клиенту для хранения, может быть зашифровано, если необходимо, и может быть сгенерирован код аутентификации сообщения (MAC), чтобы обеспечить вышеуказанные свойства. Фактически, вы могли бы иметь код управления сеансом для генерации HMAC с секретом вашего приложения, добавить его в файл cookie и заставить ваше приложение проверять MAC, чтобы убедиться, что файл cookie не был подделан. Если вам также необходимо шифрование (секретность состояния, хранящегося на клиенте), вы можете выбрать аутентифицированное шифрование (например, AES-GCM), которое обеспечивает оба свойства за один раз.
Хотя есть небольшая проблема. Допустим, у вас есть состояние сеанса, зашифрованное, аутентифицированное и сохраненное на клиенте. Состояние сеанса включает в себя роли для пользователя. У вас есть пользователь, которому вы предоставляете права администратора. Ваш пользователь достаточно умен и сохраняет свои куки на потом. Затем вы передумаете и отзовете администратора от этого пользователя. Если он отправит свой старый cookie, который имел , имеет администратора, ничто не помешает ему стать администратором. Это называется атакой replay , и если это проблема в вашем приложении, вы должны реализовать защиту вручную.
Также, скажем, два ваших приложения используют один и тот же секрет по любой причине (плохая идея в целом, но в любом случае). Зашифрованный cookie от одного может потенциально использоваться в другом, что может нанести ущерб или привести к уязвимости, если не будет обработан правильно.
Теперь, когда все это обсуждалось с потенциальными проблемами, обратите внимание, что это в точности , что JWT решает для вас (с HMAC), или JWE для зашифрованного случая. Если вы просто не изучаете эти вещи, пожалуйста, просто используйте стандартную реализацию JWT / JWE, потому что это непросто сделать правильно, а детали реализации имеют большое значение.
5 ответов
Let there be a list of many Sets named (S)
Perform a pass through all elements of S, to determine the range (LOW .. HIGH).
Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).
do
Init all elements of M to NULL.
Iterate though S, processing them one Set at a time, named (Si).
Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
For each pair examine M(P1, P2)
if M(P1, P2) is NULL
Continue with the next pair.
otherwise
Merge Si, into the Set pointed to by, M(P1, P2).
Remove Si from S, as it has been merged.
Move on to processing Set S(i + 1)
If Si was not merged,
Permutate again through Si
For each pair, make M(P1, P2) point to Si.
while At least one set was merged during the pass.
Моя голова говорит, что это о Порядке (2 Н ln N). Возьмите это с мелкой частицей соли.
Я не вижу, как это может быть сделано в меньше, чем O (n^2).
Каждый набор должен сравниться с любым, чтобы видеть, содержат ли они 2 или больше общих элемента. Это - n* (n-1)/2 сравнения, поэтому O (n^2), даже если проверка на общие элементы занимает время.
В сортировке наивная реализация является O (n^2), но можно использовать в своих интересах переходную природу заказанного сравнения (так, например, Вы ничего не знаете в более низком разделе потребностей quicksort сравниться с чем-либо в верхнем разделе, поскольку это уже сравнилось с центром). Это - то, какой результат в сортировке быть O (n * регистрируют n).
Это не применяется здесь. Таким образом, если нет что-то специальное о наборах, которое позволяет нам пропускать сравнения на основе результатов предыдущих сравнений, это будет O (n^2) в целом.
Paul.
Если можно заказать элементы в наборе, можно изучить использование Сортировки с объединением на наборах. Единственная необходимая модификация должна проверить на дубликаты во время фазы слияния. Если Вы найдены, просто удалите дубликат. Так как сортировка с объединением является O (n*log (n)), это предложит imrpoved скорость по сравнению с наивным O (n^2) алгоритм.
Однако, чтобы действительно быть эффективными, необходимо поддержать отсортированный набор и сохранить отсортированным, так, чтобы можно было пропустить фазу вида и перейти прямо к фазе слияния.
Одно примечание стороны: Это зависит от того, как часто это происходит. Если большинство пар наборов действительно совместно использует по крайней мере два элемента, могло бы быть самым эффективным создать новый набор в то же время, что и Вы ступаете через сравнение и выбрасываете его, если они не соответствуют условию. Если большинство пар не совместно использует по крайней мере два элемента, то, задерживая здание нового набора, пока подтверждение условия не могло бы быть более эффективным.
Если Ваши элементы являются числовыми по своей природе или могут быть естественно заказаны (т.е. можно назначить значение такой 1, 2, 42 и т.д....), я предложил бы использовать вид основания на объединенных наборах и сделал бы вторую передачу для взятия на уникальных элементах.
Этот алгоритм должен иметь O (n), и можно оптимизировать вид основания вполне немного использующих поразрядных операторов сдвига и битовых масок. Я сделал что-то подобное для проекта, я продолжал работать, и оно работает как очарование.