时间戳

首页 > 解决方案 > 在登录页面中循环大量帐户的最快方法是什么

python - 在登录页面中循环大量帐户的最快方法是什么

问题描述

我想知道如果我有 100 万用户，需要多长时间才能循环每个帐户以检查用户名和电子邮件，如果注册页面检查它们是否已被使用，或者检查用户名和密码是否和在登录页面中正确，如果我在传统的 for 循环中执行它会不会需要很长时间？

标签： pythonalgorithmsortingwebdata-structures

解决方案

我不会给出详细的技术答案，而是尝试给出如何解决您的担忧的理论说明。你的意思似乎是这样的：

登录用户时，线性搜索可能太慢。

我想你的想法是这样的：用户输入用户名和密码，点击一个按钮，然后你遍历一个用户名/密码组合列表，看看是否有匹配的组合。这需要的时间与系统中的用户数量呈线性关系；如果您的系统中有 100 万用户，那么循环所用的时间大约是您刚拥有 1000 用户时的一千倍……如果您有 10 亿用户，那么循环将花费一千倍的时间。

这在实践中是否是性能问题只能通过测试和需求分析来确定。但是，如果确定它是一个问题，那么理论就有一个可以拯救的地方。

想象一下我们原始方案的一个小改进：与其以任意顺序存储用户名/密码组合并每次都查看整个列表，不如想象按用户名的字母顺序存储这些组合。这使我们能够使用二进制搜索而不是线性搜索来确定是否存在匹配的用户名：

  1. 检查列表中的中间元素
  2. 如果目标元素等于中间元素，则找到匹配项
  3. 否则，如果目标元素在中间元素之前，则在列表的左半部分重复二分查找
  4. 否则，如果目标元素在中间元素之后，则在列表的右半部分重复二分查找
  5. 如果您在没有找到目标的情况下用完列表，则它不在列表中

就系统中的用户数量而言，它的时间复杂度是对数的：如果你从一千个用户增加到一百万个用户，所花费的时间大约增加了十倍，而不是实际情况下的一千倍用于线性搜索。这已经是对线性搜索的巨大改进，并且对于任何实际数量的用户来说都可能足够高效。但是，如果额外的性能测试和需求分析确定它仍然太慢，还有其他可能性。

想象一下，现在创建一个用户名/密码对的大数组，每当将一对添加到集合中时，都会使用一个函数将用户名转换为数字索引。然后将该对插入到数组中的该索引处。稍后，当您想查找该条目是否存在时，您可以使用相同的函数来计算索引，然后仅检查该索引以查看您的元素是否存在。如果将用户名映射到索引的函数（称为散列函数；索引称为散列）是完美的——不同的字符串不会映射到同一个索引——那么这会明确地告诉你你的元素是否存在。值得注意的是，在一些合理的假设下，做出此决定的时间主要与系统中当前的用户数量无关：您可以从该方案中获得（摊销的）恒定时间行为，或相当接近它的东西。这意味着从一千到一百万用户对性能的影响可能可以忽略不计。

这个答案并没有深入研究在生产系统中实现这些想法的丑陋的现实世界细节。然而，现实世界的系统可以针对所呈现的情况来实施这些想法（以及更多）。

编辑：评论要求提供一些关于在 Python 中实际实现哈希表的指示。以下是对此的一些想法。

hash()因此，如果您禁用导致它为程序的不同执行产生不同哈希值的安全功能，则可以使内置函数工作。否则，您可以import hashlib在那里使用一些哈希函数，并使用 eg 将输出转换为整数int.from_bytes。一旦你得到你的号码，你可以取模数（或除法后的余数，使用%运算符）wrt你的哈希表的容量。这为您提供了放置项目的哈希表中的索引。如果您发现那里已经有一个项目 - 即我们在理论上做出的散列函数完美的假设结果是不正确的 - 那么您需要一个策略。处理此类碰撞的两种策略是：

  1. 不要将项目放在表中的每个索引处，而是放置项目的链接列表。将项目添加到由哈希函数计算的索引处的链表中，并在进行搜索时在那里查找它们。

  2. 使用某种确定性方法（例如，平方和取模）将索引修改到某个固定次数，以查看是否可以轻松找到备份点。然后，在搜索时，如果在哈希方法计算的索引处没有找到您期望的值，则检查下一次备份，依此类推。最终，在最坏的情况下，您必须退回到类似方法 1 的方法，因为此过程可能会无限期地失败。

至于表的容量有多大：我建议研究建议，但直观地说，一般来说，最好的选择是通过一些恒定的乘法因子来创建大于必要的容量。一旦哈希表开始填满，就可以检测到这一点并扩展容量（必须重新计算所有哈希并将项目重新插入到它们的新位置 - 这是一项代价高昂的操作，但如果你以乘法方式增加容量，那么我想象这不会是一个太频繁的问题）。

推荐阅读