lkjhlklknujas_个人页

OpenAI最新发布的支持实时语音对话的模型GPT-4o在多个方面表现出色，以下是对其评价： 交互更自然：GPT-4o接受文本、音频和图像的任意组合作为输入，并生成文本、音频和图像的任意组合输出，这使得人机交互更加自然。它可以在短至232毫秒的时间内响应音频输入，平均时间为320毫秒，与人类在正常对话中的响应时间近似。这种速度使得互动流畅自然，减少了传统AI系统中常见的延迟感。视觉功能增强：GPT-4o还增强了ChatGPT的视觉功能，通过照片或屏幕截图，ChatGPT现在可以迅速回答相关问题。这种能力使得ChatGPT能够更全面地理解用户的意图和需求，提供更准确和有用的回答。情感理解能力提升：GPT-4o能够捕捉用户的语音情绪，并据此调整自己的回应方式。无论是语气、语调还是内容选择，都力求贴近用户的情感状态，仿佛是一位真正懂得共情的对话伙伴。这种情感理解能力使得GPT-4o能够提供更人性化、更有温度的对话体验。推理与编码能力强大：在文本、逻辑推理和代码生成方面，GPT-4o保持了与GPT-4 Turbo同等的高水准。同时，在处理非文本信息时，如分析代码、实时解答数学问题等，GPT-4o也展现出了前所未有的能力。这种强大的推理与编码能力使得GPT-4o能够应对各种复杂的任务和场景。记忆与连续性对话能力增强：GPT-4o的记忆能力有了质的飞跃，能够记住之前的对话内容，提供连贯、上下文相关的对话体验。这种能力增强了交流的深度和真实感，使得用户在与GPT-4o进行交流时能够感受到更加自然和流畅的对话体验。总的来说，OpenAI最新发布的GPT-4o模型在人机交互、视觉功能、情感理解、推理与编码能力以及记忆与连续性对话等方面都表现出色。它的出现将为用户带来更加自然、流畅和人性化的对话体验，有望在多个领域得到广泛应用。

提高Linux系统的稳定性可以从多个方面入手，以下是一些建议： 及时更新系统和应用程序：保持系统和应用程序的最新状态是非常重要的，因为新版本通常会修复旧版本中的漏洞和错误。使用系统自带的软件包管理工具，如apt、yum或dnf等，定期更新系统和软件包。 配置合理的内核参数：内核参数的配置对系统稳定性有很大影响。根据实际需求，调整内核参数可以避免系统崩溃或减少故障发生。可以通过修改GRUB引导加载器的配置文件或使用内核启动参数来调整内核参数。 使用高性能的硬件和网络设备：硬件设备的性能对Linux系统的稳定性也有很大影响。使用高性能的硬件和网络设备，如固态硬盘、千兆网卡等，可以提高系统的读写速度和网络稳定性。 优化系统性能：优化系统的性能可以提高系统的稳定性。例如，关闭不必要的系统服务、调整进程优先级、优化文件系统等。 定期备份数据：定期备份数据可以避免数据丢失或损坏导致系统不稳定。可以使用外部存储设备或云存储等方式进行备份。 监控系统状态：监控系统的状态可以帮助发现潜在的问题。可以使用系统自带的工具，如top、htop、sar等，或使用第三方工具，如Zabbix、Nagios等，进行系统监控。 定期进行系统健康检查：定期进行系统健康检查可以及时发现硬件故障或软件漏洞，提前进行修复和维护，避免故障扩大导致系统崩溃。可以使用系统自带的工具或第三方工具进行系统健康检查。 总之，提高Linux系统的稳定性需要从多个方面入手，包括及时更新系统和应用程序、配置合理的内核参数、使用高性能的硬件和网络设备、优化系统性能、定期备份数据、监控系统状态和定期进行系统健康检查等。

独立开发者是指那些独立工作，自行负责开发软件应用程序的人。他们通常需要具备编程技能、项目管理能力和创新思维，以独立完成软件应用程序的开发。 独立开发者的优势在于他们可以自由地选择自己感兴趣的项目，灵活地安排工作时间和工作地点，并且可以自主地决定产品的设计和功能。此外，独立开发者还可以通过自己的创意和技能，打造出独特、有价值的软件应用程序，从而获得更高的收益和成就感。 然而，独立开发者的工作也并不容易。他们需要具备强大的自我驱动力和自我管理能力，以便在缺乏团队支持和项目管理经验的情况下，保持高效的工作状态。此外，独立开发者还需要具备市场营销和推广能力，以便将自己的产品推向更广泛的用户群体。 总之，选择成为一名独立开发者需要具备一定的技能、经验和自我驱动力。如果你对这些方面有兴趣并且愿意不断学习和提高自己的能力，那么成为一名独立开发者可能会是一个有趣且富有挑战性的职业选择。

个人开发者可以通过开源项目获利，但具体获利的方式和金额因个人能力和项目不同而异。以下是一些可能获利的途径： 获得项目资金支持：一些开源项目会提供资金支持，以吸引更多的开发者参与其中。个人开发者可以通过参与这些项目，获得一定的资金支持，用于开发自己的开源项目或提高自己的技术水平。获得捐赠：一些开源项目的用户或社区可能会为项目捐赠一定的资金或物品，以支持项目的开发和维护。个人开发者可以通过参与这些项目，获得一定的捐赠，用于改善自己的生活或支持其他开源项目的开发。获得商业机会：一些开源项目可能会引起商业公司的关注，这些公司可能会考虑将该项目作为其商业产品的一部分，或者与项目维护者合作，提供更高级别的技术支持或其他服务。个人开发者可以通过参与这些项目，获得商业机会，提高自己的技术水平和知名度。获得知识和经验：参与开源项目可以帮助个人开发者提高自己的技术水平和经验，了解更多的开源社区和生态系统，学习其他优秀开发者的代码和最佳实践，从而更好地开发自己的开源项目。总之，个人开发者可以通过参与开源项目获利，但需要根据自身情况和项目特点选择合适的途径，并遵守开源许可证和社区道德准则，尊重他人的贡献和知识产权。

双11购物节已经结束，我买了很多东西。 以下是一些值得推荐的开发者物品清单： 笔记本电脑：咸鱼收了一台11代11800H的笔记本电脑，作为平时移动办公和监控后台足够用了，性能不如最新的12代13代电脑，但是胜在价格优惠，性价比高。 显示器：AOC小金刚 机械键盘：三模87键机械键盘，TTC金粉轴 云服务器：阿里云云服务ECS经济型e实例，买了一年，跑自己的docker项目完全够用。

在编程语言领域，也有一些技术升级失败的案例。其中一些比较知名的包括： Perl 6：Perl 6是Perl语言的继任者，设计目的是为了提供更高效、更简洁的编程。然而，Perl 6在发布后并没有得到广泛的采用，部分原因是其语法和语义过于复杂，难以学习，同时与其他语言的兼容性也不太好。这也导致了Perl 6并没有像Perl 5一样广泛地被使用。Visual Basic 6.0：Visual Basic 6.0是微软的一款基于事件驱动的编程语言，用于开发Windows桌面应用程序。然而，VB 6.0在发布后并没有得到广泛的升级，部分原因是其不支持Unicode编码，同时也缺乏对一些新技术的支持，如Internet Explorer 4.0。这也导致了VB 6.0并没有像后来的VB .NET一样广泛地被使用。这些失败的案例都表明了技术升级的重要性，同时也提醒我们在进行技术升级时要谨慎评估风险和可行性。

2023年云栖大会上有很多令人印象深刻的技术和产品，其中最引人注目的是通义千问2.0模型。这是阿里云发布的一款千亿级参数的大模型，相比4月发布的1.0版本，通义千问2.0在复杂指令理解、文学创作、通用数学、知识记忆、幻觉抵御等能力上均有显著提升。在10个权威测评中，通义千问2.0综合性能超过GPT-3.5，正在加速追赶GPT-4。 此外，阿里云还发布了一站式的模型应用开发平台——阿里云百炼，以及8款垂直类AI模型，包括通义晓蜜、通义星尘、通义万相、通义智文、通义法睿、通义仁心、通义千问、通义听语。这些产品和技术的发布，标志着阿里云已初步建成AI时代全栈的云计算体系。 这些产品和技术的优势在于： 降低使用门槛：通过推出千亿级参数的大模型和一站式的模型应用开发平台，阿里云降低了企业和开发者使用AI技术的门槛，使他们无需具备高深的编程技能和专业知识，就能快速创建和应用AI模型。提升工作效率：这些产品和技术的应用范围非常广泛，可以应用于自然语言处理、图像识别、语音识别、推荐系统等多个领域，帮助企业和开发者提高工作效率，减少人力成本。加速技术创新：阿里云不断推出新的技术和产品，加速了AI领域的技术创新和应用创新。这些技术和产品不仅推动了云计算的发展，也将对各行各业产生深远的影响。

阿里云发布的全球首个容器计算服务 ACS（Alibaba Cloud Container Compute Service）是一项具有重要意义的创新。以下是我对阿里云发布容器计算服务的几个观点： 创新性和领先性：阿里云发布的容器计算服务ACS是全球首个基于Kubernetes的容器计算服务。它以Kubernetes为使用界面，提供符合容器规范的算力资源，将算力交付模式升级为Serverless形态，用户无需关注底层节点及集群的运维管理。这种创新性的技术架构和实现方式，使得阿里云在容器计算领域具有了领先地位。 降低用云门槛：阿里云希望通过ACS大幅降低企业和开发者用云门槛，将Serverless理念大规模落地。通过ACS针对不同业务场景提供的K8s Pod实例类型，即通用型、任务型、独享型来匹配多样的工作负载运行需求，结合大规模资源池调度优势，帮助企业降低使用容器、Kubernetes的代价和成本。这种方式将使得更多的企业和开发者能够方便地使用容器和Kubernetes技术，加速云计算的发展。 丰富负载类型：阿里云将通过ACS支撑更为丰富的负载类型。除了传统的Web应用、微服务、大数据分析等负载类型外，阿里云还将通过ACS支持更多种类的负载，如人工智能、机器学习等。这将使得更多的应用场景能够受益于容器和Kubernetes技术的优势。 推动容器技术的发展：阿里云发布容器计算服务ACS，将进一步推动容器技术的发展。它将使得更多的企业和开发者关注容器技术，投入更多的资源来研究和应用容器技术。这将有助于推动容器技术的进步和发展。 更好的用户体验：阿里云发布的容器计算服务ACS将提供更好的用户体验。它将通过Serverless形态的算力交付模式，使得用户无需关注底层节点及集群的运维管理，从而能够更加专注于业务开发和创新。同时，通过提供符合容器规范的算力资源，用户能够更好地利用容器和Kubernetes技术的优势，实现更高效的应用开发和部署。 综上所述，阿里云发布的全球首个容器计算服务ACS是一项具有重要意义的创新。它将有助于降低用云门槛，丰富负载类型，推动容器技术的发展，并提供更好的用户体验。同时，我们也期待着阿里云在容器计算领域能够持续推出更多的创新性产品和服务，为全球企业和开发者提供更优质的云计算服务。

虚拟数字人有可能在未来替代真人主播。相比于真人主播，数字人主播具有以下优点： 成本低：数字人主播无需花费大量时间和金钱在培训、化妆、服装等方面，只需一次性定制数字人模型，就可以长期使用。这大大降低了直播成本和风险，提高了直播收益和竞争力。时间空间无限制：数字人主播不受时间和地点的限制，可以实现全年无休播报新闻。形象可控：数字人主播可以根据不同的直播主题和风格，选择不同性别、年龄、肤色、发型等外貌特征，还可以选择不同语言、方言、口音等声音特征，以及不同姿态、造型等动作特征。这样可以满足观众多元化和个性化的喜好，并且增加直播内容的吸引力和创新性。智能交互强：数字人主播可以通过AI驱动，实现实时智能互动。无需人为的操作和干预，可以自动识别和回答用户的问题，智能地控制直播间的氛围。报道更准确、及时：虚拟数字人可以24小时不间断地工作，并且能够保证直播内容的准确性和及时性，同时也能避免因人为因素导致的失误。然而，尽管数字人主播具有这些优点，但它们并不能完全取代真人主播。真人主播具有独特的个性和情感，能够与观众建立真实的人际互动关系，这是目前数字人主播无法做到的。此外，真人主播还能够根据自身的经验和知识储备，对直播内容进行更为深入的解读和讨论。 因此，数字人主播和真人主播各有其优势和局限性，在未来它们很可能会共同存在，相互补充。数字人主播可以承担一些重复性较高、简单繁琐的任务，而真人主播则可以负责更为复杂、需要深度思考和人际互动的工作。这样的结合将能够更好地满足观众的需求，并为直播行业带来更大的价值。

参加参加！

在云时代下，为了便捷高效地管理企业数据，可以考虑以下几点： 数据分类和归档：将企业数据进行分类和归档，以便更好地管理和使用。可以根据不同的业务需求，将数据分为不同的类别，例如客户数据、产品数据、财务数据等，然后将其存储在不同的云存储桶或文件夹中。数据备份和恢复：为了防止数据丢失和损坏，需要定期备份数据，并确保备份数据的可用性和完整性。同时，也需要能够在需要时快速恢复数据。数据安全和隐私保护：在云时代下，数据安全和隐私保护至关重要。需要采取必要的安全措施，例如数据加密、访问控制、安全审计等，以确保数据的机密性和完整性。数据治理和管理：建立数据治理和管理策略，以确保数据的合规性和可管理性。这包括定义数据的标准、制定数据管理流程、建立数据管理团队等。利用云服务提供商的服务：选择合适的云服务提供商，例如阿里云、腾讯云等，利用它们提供的云存储、云数据库、云服务器等服务，可以更加便捷高效地管理企业数据。培训和管理员的专业能力提升：加强员工和管理员的培训，提高他们对云时代下数据管理的认识和技能水平。同时，也需要关注管理员的专业能力提升，例如操作系统、网络技术、虚拟化技术等。综上所述，在云时代下，为了便捷高效地管理企业数据，需要综合考虑数据的分类和归档、备份和恢复、安全和隐私保护、治理和管理以及利用云服务提供商的服务等方面，并加强培训和管理员的专业能力提升。

在云时代下，为了便捷高效地管理企业数据，可以考虑以下几点： 数据分类和归档：将企业数据进行分类和归档，以便更好地管理和使用。可以根据不同的业务需求，将数据分为不同的类别，例如客户数据、产品数据、财务数据等，然后将其存储在不同的云存储桶或文件夹中。数据备份和恢复：为了防止数据丢失和损坏，需要定期备份数据，并确保备份数据的可用性和完整性。同时，也需要能够在需要时快速恢复数据。数据安全和隐私保护：在云时代下，数据安全和隐私保护至关重要。需要采取必要的安全措施，例如数据加密、访问控制、安全审计等，以确保数据的机密性和完整性。数据治理和管理：建立数据治理和管理策略，以确保数据的合规性和可管理性。这包括定义数据的标准、制定数据管理流程、建立数据管理团队等。利用云服务提供商的服务：选择合适的云服务提供商，例如阿里云、腾讯云等，利用它们提供的云存储、云数据库、云服务器等服务，可以更加便捷高效地管理企业数据。培训和管理员的专业能力提升：加强员工和管理员的培训，提高他们对云时代下数据管理的认识和技能水平。同时，也需要关注管理员的专业能力提升，例如操作系统、网络技术、虚拟化技术等。综上所述，在云时代下，为了便捷高效地管理企业数据，需要综合考虑数据的分类和归档、备份和恢复、安全和隐私保护、治理和管理以及利用云服务提供商的服务等方面，并加强培训和管理员的专业能力提升。

如果AI能够参加亚运会，它们可能会在以下项目上表现出色： 电子竞技：AI在电子竞技领域已经取得了显著的成果，如AlphaGo在围棋比赛中的胜利。在不同类型的电子竞技中，AI可能会展现出卓越的反应速度、精确的操作和强大的战略思维，成为顶级选手。射箭：AI可以通过机器学习和数据分析，精确计算射击的力度、方向和风向等因素，从而提高射击的准确性和稳定性。田径项目：AI可能在长跑、短跑和跳远等项目中表现出色。它可以通过优化步频、姿势和力量的分配来实现最佳的运动表现。总之，如果AI能够参加亚运会，它们可能会在电子竞技、射箭、田径项目等表现出色。但是，由于AI的技术和算法的限制，它们可能无法完全取代人类运动员在某些领域中的表现。

AIGC是通向AGI的一条路径。 AIGC是一种人工智能技术，旨在通过模拟人类思维和行为的方式，实现更加智能化的应用。在AGI的追求中，AIGC技术可以作为一种工具，帮助人工智能系统更好地理解和处理复杂的信息，从而更加智能化地完成任务。 但是，AIGC并不是实现AGI的唯一路径，还有其他的技术和方法也在探索中。

AI应用开发可以通过以下几种方式来简化开发过程： 使用现成的AI平台和工具：现在有很多现成的AI平台和工具，如TensorFlow、PyTorch、Google Cloud Platform等，这些工具提供了大量的预先构建好的模块和库，可以用来快速构建AI应用。找到合适的开源模型：很多AI应用都可以找到合适的开源模型，这些模型已经经过了训练和优化，可以直接使用。如果找不到合适的开源模型，也可以使用AI平台提供的模型训练服务，通过上传数据并指定训练目标来训练自己的模型。简化模型训练过程：模型训练是AI应用开发中比较耗时和复杂的过程，可以通过使用GPU来加速训练过程，或者使用模型剪枝、量化等技术来减少模型的复杂度和训练时间。优化模型部署流程：模型部署是AI应用开发中比较重要的一个环节，可以通过使用容器技术、微服务等技术来优化模型部署流程，使得模型能够快速、稳定地部署到生产环境中。利用AI平台的自动化工具：很多AI平台都提供了自动化工具，如AutoML、Hyperparameter Tuning等，这些工具可以帮助开发者自动进行模型选择、参数优化等过程，从而减少手动调参的时间和成本。参考其他成功的案例：通过参考其他成功的案例，可以了解其他开发者是如何成功地构建类似的AI应用的，从而获得一些启示和灵感。总之，AI应用开发需要综合运用各种技术和工具，通过不断地实践和学习，不断地优化和改进开发过程，才能提高开发效率和质量。

每个开发者是否应该拥有一台云服务器，这取决于他们的具体需求和项目规模。 对于一些开发者，拥有一台云服务器可能是必要的，尤其是那些需要进行复杂计算、存储大量数据或需要提供实时服务的应用程序。此外，云服务器也可以提供更好的安全性和可靠性，以及更灵活的扩展性，能够更好地满足一些特定需求。 然而，对于一些小型项目或个人开发者，他们可能不需要云服务器，因为他们的应用程序并不需要那么多的计算和存储资源，或者他们可以使用其他云计算服务来满足他们的需求。 总的来说，是否应该拥有一台云服务器取决于开发者的具体需求和项目规模。对于需要云服务器来支持其应用程序的开发者来说，拥有一台云服务器是有必要的，但对于其他开发者来说，他们可以选择使用其他云计算服务来满足其需求。

对于程序员来说，技术能力和业务逻辑都是非常重要的。 技术能力是程序员的核心竞争力之一，它包括了编程语言、算法、数据结构、设计模式等技能。这些技能可以帮助程序员更好地编写代码，提高代码的质量和可维护性。同时，技术能力也是程序员学习和适应新技术的基础。 业务逻辑则是程序员理解公司或客户业务的关键，它可以帮助程序员更好地理解需求，编写出更符合业务需求的代码。在开发过程中，业务逻辑也能够帮助程序员更好地与产品经理、测试人员等进行有效的沟通和协作。 因此，技术能力和业务逻辑是相辅相成的，不能简单地说哪个更重要。对于程序员来说，不断学习和提高自己的技术能力是非常重要的，同时也要注重理解业务逻辑，提高自己的业务水平。只有这样，才能更好地适应不断变化的市场需求和技术环境。

积极参与

云计算的第三次浪潮是人工智能与云计算的结合，它正在引领着云计算的第三次浪潮。这一浪潮并非瞬息而至，也不会在短期内完成，而是需要长达十年甚至几十年的时间来逐步实现。 在这次浪潮中，云计算不再仅仅是提供计算能力和存储空间，而是通过人工智能技术，将数据转化为有价值的信息和知识，从而为人类社会的发展带来巨大的推动力。这种结合带来了巨大的机遇，同时也带来了一系列的挑战和问题，例如如何保护个人隐私、如何保障数据安全、如何应对技术变革带来的失业问题等等。 对于云计算的第三次浪潮，我们需要认识到它的重要性，同时也需要积极应对它带来的挑战和问题。在这个过程中，我们需要全社会共同努力，寻找解决方案。总的来说，云计算的第三次浪潮将会成为推动社会进步的重要力量。

1.1 引言 你将学习使用K最近邻算法编写推荐系统； 有些问题在有限的时间内是不可解的！书中讨论NP完全问题的部分将告诉你，如何识别这样的问题以及如何设计找到近似答案的算法。 1.2 二分查找 如果你的用户名为karlmageddon, Facebook可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。 二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。 你可能不记得什么是对数了，但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个：10 × 10=100。因此，log10100=2。对数运算是幂运算的逆运算。 1.3 大O表示法 实际上，Bob错了，而且错得离谱。列表包含10亿个元素时，简单查找需要10亿毫秒，相当于11天！为什么会这样呢？因为二分查找和简单查找的运行时间的增速不同。 也就是说，随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。 大O表示法指出了最糟情况下的运行时间 除最糟情况下的运行时间外，还应考虑平均情况的运行时间，这很重要。最糟情况和平均情况将在第4章讨论。 O(n)，也叫线性时间，这样的算法包括简单查找。❑ O(n ＊ log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。❑ O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。❑ O(n! )，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。 算法的速度指的并非时间，而是操作数的增速。 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。 O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。 1.4 小结 算法运行时间并不以秒为单位。 算法运行时间是从其增速的角度度量的。 2.1 内存的工作原理 计算机就像是很多抽屉的集合体，每个抽屉都有地址。 接下来介绍数组和链表以及它们的优缺点。 2.2 数组和链表 一种解决之道是“预留座位”：即便当前只有3个待办事项，也请计算机提供10个位置，以防需要添加待办事项。这样，只要待办事项不超过10个，就无需转移。这是一个不错的权变措施，但你应该明白，它存在如下两个缺点。 ❑ 你额外请求的位置可能根本用不上，这将浪费内存。你没有使用，别人也用不了。❑ 待办事项超过10个后，你还得转移。 对于这种问题，可使用链表来解决。 这犹如寻宝游戏。 排行榜网站使用卑鄙的手段来增加页面浏览量。它们不在一个页面中显示整个排行榜，而将排行榜的每项内容都放在一个页面中，并让你单击Next来查看下一项内容。例如，显示十大电视反派时，不在一个页面中显示整个排行榜，而是先显示第十大反派（Newman）。你必须在每个页面中单击Next，才能看到第一大反派（Gustavo Fring）。这让网站能够在10个页面中显示广告，但用户需要单击Next九次才能看到第一个，真的是很烦。 [插图]链表存在类似的问题。 但如果你需要跳跃，链表的效率真的很低。 元素的位置称为索引。 3.1 递归 这个盒子里有盒子，而盒子里的盒子又有盒子。钥匙就在某个盒子中。为找到钥匙，你将使用什么算法？ (1) 检查盒子中的每样东西。(2) 如果是盒子，就回到第一步。(3) 如果是钥匙，就大功告成！ 递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。我很喜欢Leigh Caldwell在StackOverflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。” 很多算法都使用了递归，因此理解这种概念很重要。 3.3 栈 [插图]本节将介绍一个重要的编程概念——调用栈（call stack）。调用栈不仅对编程来说很重要，使用递归时也必须理解这个概念。 递归函数也使用调用栈！ 原来“盒子堆”存储在了栈中！这个栈包含未完成的函数调用，每个函数调用都包含还未检查完的盒子。使用栈很方便，因为你无需自己跟踪盒子堆——栈替你这样做了。 使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。 ❑ 重新编写代码，转而使用循环。❑ 使用尾递归。这是一个高级递归主题，不在本书的讨论范围内。另外，并非所有的语言都支持尾递归。 3.4 小结 每个递归函数都有两个条件：基线条件和递归条件。 所有函数调用都进入调用栈。 调用栈可能很长，这将占用大量的内存。 4.1 分而治之 使用D&C解决问题的过程包括两个步骤。(1) 找出基线条件，这种条件必须尽可能简单。(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。 首先，找出基线条件。最容易处理的情况是，一条边的长度是另一条边的整数倍。 如果一边长25m，另一边长50m，那么可使用的最大方块为25m×25m。 现在需要找出递归条件，这正是D&C的用武之地。根据D&C的定义，每次递归调用都必须缩小问题的规模。如何缩小前述问题的规模呢？我们首先找出这块地可容纳的最大方块。 欧几里得算法前面说“适用于这小块地的最大方块，也是适用于整块地的最大方块”，如果你觉得这一点不好理解，也不用担心。这确实不好理解，但遗憾的是，要证明这一点，需要的篇幅有点长，在本书中无法这样做，因此你只能选择相信这种说法是正确的。如果你想搞明白其中的原因，可参阅欧几里得算法。 接下来，从这块土地中划出最大的方块，余下一块更小的土地。 余下的这块土地满足基线条件，因为160是80的整数倍。将这块土地分成两个方块后，将不会余下任何土地！ 第一步：找出基线条件。最简单的数组什么样呢？请想想这个问题，再接着往下读。如果数组不包含任何元素或只包含一个元素，计算总和将非常容易。 第二步：每次递归调用都必须离空数组更近一步。 别忘了，递归记录了状态。 提示编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。 诸如Haskell等函数式编程语言没有循环，因此你只能使用递归来编写这样的函数。如果你对递归有深入的认识，函数式编程语言学习起来将更容易。 符合基线条件时运行第一个定义，符合递归条件时运行第二个定义。 4.2 快速排序 快速排序是一种常用的排序算法，比选择排序快得多。例如，C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了D&C。 下面来使用快速排序对数组进行排序。对排序算法来说，最简单的数组什么样呢？还记得前一节的“提示”吗？就是根本不需要排序的数组。 接下来，找出比基准值小的元素以及比基准值大的元素。 这被称为分区（partitioning）。现在你有：❑ 一个由所有小于基准值的数字组成的子数组；❑ 基准值；❑ 一个由所有大于基准值的数组组成的子数组。 这里只是进行了分区，得到的两个子数组是无序的。但如果这两个数组是有序的，对整个数组进行排序将非常容易。 如果子数组是有序的，就可以像下面这样合并得到一个有序的数组：左边的数组+基准值+右边的数组。 这个子数组都只有一个元素，而你知道如何对这些数组进行排序。 (1) 选择基准值。(2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。(3) 对这两个子数组进行快速排序。 归纳证明刚才你大致见识了归纳证明！归纳证明是一种证明算法行之有效的方式，它分两步：基线条件和归纳条件。是不是有点似曾相识的感觉？例如，假设我要证明我能爬到梯子的最上面。递归条件是这样的：如果我站在一个横档上，就能将脚放到上一个横档上。换言之，如果我站在第二个横档上，就能爬到第三个横档。这就是归纳条件。而基线条件是这样的，即我已经站在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端。 4.3 再谈大O表示法 快速排序的独特之处在于，其速度取决于选择的基准值。 来看看第2章介绍的选择排序，其运行时间为O(n2)，速度非常慢。 还有一种名为合并排序（merge sort）的排序算法，其运行时间为O(n logn)，比选择排序快得多！快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。 与选择排序一样慢！但这是最糟情况。在平均情况下，快速排序的运行时间为O(n log n)。 ❑ 这里说的最糟情况和平均情况是什么意思呢？❑ 若快速排序在平均情况下的运行时间为O(n log n)，而合并排序的运行时间总是O(n log n)，为何不使用合并排序？它不是更快吗？ c是算法所需的固定时间量，被称为常量。例如，print_items所需的时间可能是10毫秒＊n，而print_items2所需的时间为1秒 ＊ n。 通常不考虑这个常量，因为如果两种算法的大O运行时间不同，这种常量将无关紧要。 但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。 这里要告诉你的是，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。 5.1 散列函数 散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。 如果用专业术语来表达的话，我们会说，散列函数“将输入映射到数字”。你可能认为散列函数输出的数字没什么规律，但其实散列函数必须满足一些要求。 ❑ 它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都必须为4。如果不是这样，散列表将毫无用处。 ❑ 它应将不同的输入映射到不同的数字。例如，如果一个散列函数不管输入是什么都返回1，它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。 散列函数总是将同样的输入映射到相同的索引。每次你输入avocado，得到的都是同一个数字。因此，你可首先使用它来确定将鳄梨的价格存储在什么地方，并在以后使用它来确定鳄梨的价格存储在什么地方。 散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会返回无效索引100。 你可能根本不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的散列表实现为字典，你可使用函数dict来创建散列表。 5.2 应用案例 将散列表用于查找 无论你访问哪个网站，其网址都必须转换为IP地址。 这不是将网址映射到IP地址吗？好像非常适合使用散列表啰！这个过程被称为DNS解析（DNS resolution），散列表是提供这种功能的方式之一。 首先来投票的是Tom，上述代码打印letthem vote!。接着Mike来投票，打印的也是let them vote!。然后，Mike又来投票，于是打印的就是kick themout!。 来看最后一个应用案例：缓存。如果你在网站工作，可能听说过进行缓存是一种不错的做法。下面简要地介绍其中的原理。假设你访问网站http://facebook.com。 (1) 你向Facebook的服务器发出请求。(2) 服务器做些处理，生成一个网页并将其发送给你。(3) 你获得一个网页。 现在假设她老问你月球离地球多远，很快你就记住了月球离地球238900英里。因此不必再去Google搜索，你就可以直接告诉她答案。这就是缓存的工作原理：网站将数据记住，而不再重新计算。 如果你登录了Facebook，你看到的所有内容都是为你定制的。你每次访问http://facebook.com，其服务器都需考虑你感兴趣的是什么内容。但如果你没有登录，看到的将是登录页面。每个人看到的登录页面都相同。Facebook被反复要求做同样的事情：“当我注销时，请向我显示主页。”有鉴于此，它不让服务器去生成主页，而是将主页存储起来，并在需要时将其直接发送给用户。 这就是缓存，具有如下两个优点。❑ 用户能够更快地看到网页，就像你记住了月球与地球之间的距离时一样。下次你侄女再问你时，你就不用再使用Google搜索，立刻就可以告诉她答案。❑ Facebook需要做的工作更少。 缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！ Facebook不仅缓存主页，还缓存About页面、Contact页面、Termsand Conditions页面等众多其他的页面。因此，它需要将页面URL映射到页面数据。 当你访问Facebook的页面时，它首先检查散列表中是否存储了该页面。 仅当URL不在缓存中时，你才让服务器做些处理，并将处理生成的数据存储到缓存中，再返回它。这样，当下次有人请求该URL时，你就可以直接发送缓存中的数据，而不用再让服务器进行处理了。 5.3 冲突 处理冲突的方式很多，最简单的办法如下：如果两个键映射到了同一个位置，就在这个位置存储一个链表。 ❑ 散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。❑ 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很好，这些链表就不会很长！ 散列函数很重要，好的散列函数很少导致冲突。那么，如何选择好的散列函数呢？这将在下一节介绍！ 5.4 性能 一条水平线，看到了吧？这意味着无论散列表包含一个元素还是10亿个元素，从其中获取数据所需的时间都相同。 6.3 广度优先搜索 广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。❑ 第一类问题：从节点A出发，有前往节点B的路径吗？❑ 第二类问题：从节点A出发，前往节点B的哪条路径最短？ 在你看来，一度关系胜过二度关系，二度关系胜过三度关系，以此类推。因此，你应先在一度关系中搜索，确定其中没有芒果销售商后，才在二度关系中搜索。广度优先搜索就是这样做的！ 你也可以这样看，一度关系在二度关系之前加入查找名单。 广度优先搜索必用队列 记住这句话 有一个可实现这种目的的数据结构，那就是队列（queue）。有一个可实现这种目的的数据结构，那就是队列（queue）。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车。队列的工作原理与此相同。队列类似于栈，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。 队列是一种先进先出（First In FirstOut, FIFO）的数据结构，而栈是一种后进先出（Last In First Out, LIFO）的数据结构。 6.4 实现图 首先，需要使用代码来实现图。图由多个节点组成。 每个节点都与邻近节点相连，如果表示类似于“你→Bob”这样的关系呢？好在你知道的一种结构让你能够表示这种关系，它就是散列表！ 记住，散列表让你能够将键映射到值。在这里，你要将节点映射到其所有邻居。 6.5 实现算法 说明更新队列时，我使用术语“入队”和“出队”，但你也可能遇到术语“压入”和“弹出”。压入大致相当于入队，而弹出大致相当于出队。 首先，创建一个队列。在Python中，可使用函数deque来创建一个双端队列。 这个算法将不断执行，直到满足以下条件之一：❑ 找到一位芒果销售商；❑ 队列变成空的，这意味着你的人际关系网中没有芒果销售商。 检查一个人之前，要确认之前没检查过他，这很重要。为此，你可使用一个列表来记录检查过的人。 7.4 负权边 如果有负权边，就不能使用狄克斯特拉算法。因为负权边会导致这种算法不管用。 8.1 教室调度问题 很多人都跟我说，这个算法太容易、太显而易见，肯定不对。但这正是贪婪算法的优点——简单易行！贪婪算法很简单：每步都采取最优的做法。 8.2 背包问题 从这个示例你得到了如下启示：在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。 8.3 集合覆盖问题 使用下面的贪婪算法可得到非常接近的解。(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。(2) 重复第一步，直到覆盖了所有的州。 判断近似算法优劣的标准如下：❑ 速度有多快；❑ 得到的近似解与最优解的接近程度。 贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法的运行时间为O(n2)，其中n为广播台数量。 ❑ 集合类似于列表，只是不能包含重复的元素；❑ 你可执行一些有趣的集合运算，如并集、交集和差集。 8.4 NP完全问题 这两条路线相同还是不同你可能认为这两条路线相同，难道从旧金山到马林的距离与从马林到旧金山的距离不同吗？不一定。有些城市（如旧金山）有很多单行线，因此你无法按原路返回。你可能需要离开原路行驶一两英里才能找到上高速的匝道。因此，这两条路线不一定相同。 NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。 Jonah需要组建一个满足所有这些要求的球队，可名额有限。等等，Jonah突然间意识到，这不就是一个集合覆盖问题吗！ Jonah可使用前面介绍的近似算法来组建球队。(1) 找出符合最多要求的球员。(2) 不断重复这个过程，直到球队满足要求（或球队名额已满）。 NP完全问题无处不在！如果能够判断出要解决的问题属于NP完全问题就好了，这样就不用去寻找完美的解决方案，而是使用近似算法即可。但要判断问题是不是NP完全问题很难，易于解决的问题和NP完全问题的差别通常很小。 简言之，没办法判断问题是不是NP完全问题，但还是有一些蛛丝马迹可循的。❑ 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。❑ 涉及“所有组合”的问题通常是NP完全问题。❑ 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。❑ 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。❑ 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。❑ 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。 8.5 小结 ❑ 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。❑ 对于NP完全问题，还没有找到快速解决方案。❑ 面临NP完全问题时，最佳的做法是使用近似算法。❑ 贪婪算法易于实现、运行速度快，是不错的近似算法。 第9章 动态规划 ❑ 学习动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题。❑ 学习如何设计问题的动态规划解决方案。 9.1 背包问题 对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。 动态规划是一个难以理解的概念，如果你没有立即搞懂，也不用担心，我们将研究很多示例。 此时你很可能心存疑惑：原来的问题说的是4磅的背包，我们为何要考虑容量为1磅、2磅等的背包呢？前面说过，动态规划从小问题着手，逐步解决大问题。这里解决的子问题将帮助你解决大问题。请接着往下读，稍后你就会明白的。 9.2 背包问题FAQ 使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。 但使用贪婪算法可轻松地处理这种情况！首先，尽可能多地拿价值最高的商品；如果拿光了，再尽可能多地拿价值次高的商品，以此类推。 动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。 最优解可能导致背包没装满吗完全可能。假设你还可以偷一颗钻石。这颗钻石非常大，重达3.5磅，价值100万美元，比其他商品都值钱得多。你绝对应该把它给偷了！但当你这样做时，余下的容量只有0.5磅，别的什么都装不下。 9.3 最长公共子串 ❑ 动态规划可帮助你在给定约束条件下找到最优解。在背包问题中，你必须在背包容量给定的情况下，偷到价值最高的商品。❑ 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。 要设计出动态规划解决方案可能很难，这正是本节要介绍的。下面是一些通用的小贴士。❑ 每种动态规划解决方案都涉及网格。❑ 单元格中的值通常就是你要优化的值。在前面的背包问题中，单元格的值为商品的价值。❑ 每个单元格都是一个子问题，因此你应考虑如何将问题分成子问题，这有助于你找出网格的坐标轴。 用于解决这个问题的网格是什么样的呢？要确定这一点，你得回答如下问题。❑ 单元格中的值是什么？❑ 如何将这个问题划分为子问题？❑ 网格的坐标轴是什么？ 计算机科学家有时会开玩笑说，那就使用费曼算法（Feynmanalgorithm）。这个算法是以著名物理学家理查德·费曼命名的，其步骤如下。(1) 将问题写下来。(2) 好好思考。(3) 将答案写下来。 计算机科学家真是一群不按常理出牌的人啊！ 需要注意的一点是，这个问题的最终答案并不在最后一个单元格中！对于前面的背包问题，最终答案总是在最后的单元格中。但对于最长公共子串问题，答案为网格中最大的数字——它可能并不位于最后的单元格中。 我们回到最初的问题：哪个单词与hish更像？hish和fish的最长公共子串包含三个字母，而hish和vista的最长公共子串包含两个字母。因此Alex很可能原本要输入的是fish。 动态规划都有哪些实际应用呢？❑ 生物学家根据最长公共序列来确定DNA链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。❑ 你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。❑ 前面讨论了字符串的相似程度。编辑距离（levenshteindistance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。❑ 你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！ 9.4 小结 ❑ 需要在给定约束条件下优化某种指标时，动态规划很有用。❑ 问题可分解为离散子问题时，可使用动态规划来解决。❑ 每种动态规划解决方案都涉及网格。❑ 单元格中的值通常就是你要优化的值。❑ 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。❑ 没有放之四海皆准的计算动态规划解决方案的公式。 第10章 K最近邻算法 ❑ 学习使用K最近邻算法创建分类系统。❑ 学习特征抽取。❑ 学习回归，即预测数值，如明天的股价或用户对某部电影的喜欢程度。❑ 学习K最近邻算法的应用案例和局限性。 10.1 橙子还是柚子 请看右边的水果，是橙子还是柚子呢？我知道，柚子通常比橙子更大、更红。 如果判断这个水果是橙子还是柚子呢？一种办法是看它的邻居。来看看离它最近的三个邻居。 在这三个邻居中，橙子比柚子多，因此这个水果很可能是橙子。祝贺你，你刚才就是使用K最近邻（k-nearestneighbours, KNN）算法进行了分类！这个算法非常简单。 KNN算法虽然简单却很有用！要对东西进行分类时，可首先尝试这种算法。下面来看一个更真实的例子。 10.2 创建推荐系统 假设你是Netflix，要为用户创建一个电影推荐系统。从本质上说，这类似于前面的水果问题！ 你可以将所有用户都放入一个图表中。[插图]这些用户在图表中的位置取决于其喜好，因此喜好相似的用户距离较近。假设你要向Priyanka推荐电影，可以找出五位与他最接近的用户。 假设在对电影的喜好方面，Justin、JC、Joey、Lance和Chris都与Priyanka差不多，因此他们喜欢的电影很可能Priyanka也喜欢！ 有了这样的图表以后，创建推荐系统就将易如反掌：只要是Justin喜欢的电影，就将其推荐给Priyanka。 但还有一个重要的问题没有解决。在前面的图表中，相似的用户相距较近，但如何确定两位用户的相似程度呢？ 从上图可知，水果A和B比较像。下面来度量它们有多像。要计算两点的距离，可使用毕达哥拉斯公式。 假设你要比较的是Netflix用户，就需要以某种方式将他们放到图表中。因此，你需要将每位用户都转换为一组坐标，就像前面对水果所做的那样。 下面是一种将用户转换为一组数字的方式。用户注册时，要求他们指出对各种电影的喜欢程度。这样，对于每位用户，都将获得一组数字！ 这个距离公式很灵活，即便涉及很多个数字，依然可以使用它来计算距离。你可能会问，涉及5个数字时，距离意味着什么呢？这种距离指出了两组数字之间的相似程度。 太好了！现在要向Priyanka推荐电影将易如反掌：只要是Justin喜欢的电影，就将其推荐给Priyanka，反之亦然。你这就创建了一个电影推荐系统！ 如果你是Netflix用户，Netflix将不断提醒你：多给电影评分吧，你评论的电影越多，给你的推荐就越准确。现在你明白了其中的原因：你评论的电影越多，Netflix就越能准确地判断出你与哪些用户类似。 你求这些人打的分的平均值，结果为4.2。这就是回归（regression）。你将使用KNN来做两项基本工作——分类和回归： ❑ 分类就是编组；❑ 回归就是预测结果（如一个数字）。 回归很有用。假设你在伯克利开个小小的面包店，每天都做新鲜面包，需要根据如下一组特征预测当天该烤多少条面包：❑ 天气指数1～5（1表示天气很糟，5表示天气非常好）；❑ 是不是周末或节假日（周末或节假日为1，否则为0）；❑ 有没有活动（1表示有，0表示没有）。你还有一些历史数据，记录了在各种不同的日子里售出的面包数量。 今天是周末，天气不错。根据这些数据，预测你今天能售出多少条面包呢？我们来使用KNN算法，其中的K为4。首先，找出与今天最接近的4个邻居。 将这些天售出的面包数平均，结果为218.75。这就是你今天要烤的面包数！ 余弦相似度前面计算两位用户的距离时，使用的都是距离公式。还有更合适的公式吗？在实际工作中，经常使用余弦相似度（cosine similarity）。假设有两位品味类似的用户，但其中一位打分时更保守。他们都很喜欢Manmohan Desai的电影AmarAkbar Anthony，但Paul给了5星，而Rowan只给4星。如果你使用距离公式，这两位用户可能不是邻居，虽然他们的品味非常接近。余弦相似度不计算两个矢量的距离，而比较它们的角度，因此更适合处理前面所说的情况。本书不讨论余弦相似度，但如果你要使用KNN，就一定要研究研究它！ 所谓合适的特征，就是：❑ 与要推荐的电影紧密相关的特征；❑ 不偏不倚的特征（例如，如果只让用户给喜剧片打分，就无法判断他们是否喜欢动作片）。 你认为评分是不错的电影推荐指标吗？我给The Wire的评分可能比HouseHunters高，但实际上我观看HouseHunters的时间更长。该如何改进Netflix的推荐系统呢？ 在挑选合适的特征方面，没有放之四海皆准的法则，你必须考虑到各种需要考虑的因素。 10.3 机器学习简介 KNN算法真的是很有用，堪称你进入神奇的机器学习领域的领路人！机器学习旨在让计算机更聪明。你见过一个机器学习的例子：创建推荐系统。下面再来看看其他一些例子。 OCR指的是光学字符识别（opticalcharacter recognition），这意味着你可拍摄印刷页面的照片，计算机将自动识别出其中的文字。Google使用OCR来实现图书数字化。OCR是如何工作的呢？我们来看一个例子。请看下面的数字。 如何自动识别出这个数字是什么呢？可使用KNN。(1) 浏览大量的数字图像，将这些数字的特征提取出来。(2) 遇到新图像时，你提取该图像的特征，再找出它最近的邻居都是谁！ 一般而言，OCR算法提取线段、点和曲线等特征。 OCR的第一步是查看大量的数字图像并提取特征，这被称为训练（training）。大多数机器学习算法都包含训练的步骤：要让计算机完成任务，必须先训练它。下一个示例是垃圾邮件过滤器，其中也包含训练的步骤。 垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器（Naive Bayesclassifier），你首先需要使用一些数据对这个分类器进行训练。 朴素贝叶斯分类器也是一种简单而极其有效的算法。我们钟爱这样的算法！ 未来很难预测，由于涉及的变数太多，这几乎是不可能完成的任务。 11.1 树 对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。 然而，二叉查找树的插入和删除操作的速度要快得多。 如果你对数据库或高级数据结构感兴趣，请研究如下数据结构：B树，红黑树，堆，伸展树。 11.2 反向索引 这种数据结构被称为反向索引（invertedindex），常用于创建搜索引擎。 11.3 傅里叶变换 绝妙、优雅且应用广泛的算法少之又少，傅里叶变换算是一个。BetterExplained是一个杰出的网站，致力于以通俗易懂的语言阐释数学，它就傅里叶变换做了一个绝佳的比喻：给它一杯冰沙，它能告诉你其中包含哪些成分[插图]。换言之，给定一首歌曲，傅里叶变换能够将其中的各种频率分离出来。 这种理念虽然简单，应用却极其广泛。例如，如果能够将歌曲分解为不同的频率，就可强化你关心的部分，如强化低音并隐藏高音。傅里叶变换非常适合用于处理信号，可使用它来压缩音乐。为此，首先需要将音频文件分解为音符。傅里叶变换能够准确地指出各个音符对整个歌曲的贡献，让你能够将不重要的音符删除。这就是MP3格式的工作原理！ 数字信号并非只有音乐一种类型。JPG也是一种压缩格式，也采用了刚才说的工作原理。傅里叶变换还被用来地震预测和DNA分析。 使用傅里叶变换可创建类似于Shazam这样的音乐识别软件。傅里叶变换的用途极其广泛，你遇到它的可能性极高！ 11.4 并行算法 为提高算法的速度，你需要让它们能够在多个内核中并行地执行！ 并行算法设计起来很难，要确保它们能够正确地工作并实现期望的速度提升也很难。有一点是确定的，那就是速度的提升并非线性的，因此即便你的笔记本电脑装备了两个而不是一个内核，算法的速度也不可能提高一倍，其中的原因有两个。 并行性管理开销。假设你要对一个包含1000个元素的数组进行排序，如何在两个内核之间分配这项任务呢？如果让每个内核对其中500个元素进行排序，再将两个排好序的数组合并成一个有序数组，那么合并也是需要时间的。❑ 负载均衡。假设你需要完成10个任务，因此你给每个内核都分配5个任务。但分配给内核A的任务都很容易，10秒钟就完成了，而分配给内核B的任务都很难，1分钟才完成。这意味着有那么50秒，内核B在忙死忙活，而内核A却闲得很！你如何均匀地分配工作，让两个内核都一样忙呢？ 要改善性能和可扩展性，并行算法可能是不错的选择！ 11.5 MapReduce 有一种特殊的并行算法正越来越流行，它就是分布式算法。在并行算法只需两到四个内核时，完全可以在笔记本电脑上运行它，但如果需要数百个内核呢？在这种情况下，可让算法在多台计算机上运行。MapReduce是一种流行的分布式算法，你可通过流行的开源工具Apache Hadoop来使用它。 分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。 归并函数可能令人迷惑，其理念是将很多项归并为一项。映射是将一个数组转换为另一个数组。 而归并是将一个数组转换为一个元素。 11.6 布隆过滤器和HyperLogLog 布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。为判断网页以前是否已搜集，可不使用散列表，而使用布隆过滤器。使用散列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的。 ❑ 可能出现错报的情况，即Google可能指出“这个网站已搜集”，但实际上并没有搜集。❑ 不可能出现漏报的情况，即如果布隆过滤器说“这个网站未搜集”，就肯定未搜集。 布隆过滤器的优点在于占用的存储空间很少。使用散列表时，必须存储Google搜集过的所有URL，但使用布隆过滤器时不用这样做。布隆过滤器非常适合用于不要求答案绝对准确的情况，前面所有的示例都是这样的。对http://bit.ly而言，这样说完全可行：“我们认为这个网站可能是恶意的，请倍加小心。” 面临海量数据且只要求答案八九不离十时，可考虑使用概率型算法！ 11.7 SHA算法 另一种散列函数是安全散列算法（secure hash algorithm, SHA）函数。 说明SHA生成的散列值很长，这里截短了。你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。假设你有一个4 GB的文件，并要检查朋友是否也有这个大型文件。为此，你不用通过电子邮件将这个大型文件发送给朋友，而可计算它们的SHA散列值，再对结果进行比较。 SHA还让你能在不知道原始字符串的情况下对其进行比较。例如，假设Gmail遭到攻击，攻击者窃取了所有的密码！你的密码暴露了吗？没有，因为Google存储的并非密码，而是密码的SHA散列值！你输入密码时，Google计算其散列值，并将结果同其数据库中的散列值进行比较。 Google只是比较散列值，因此不必存储你的密码！SHA被广泛用于计算密码的散列值。这种散列算法是单向的。你可根据字符串计算出散列值。 当前，最安全的密码散列函数是bcrypt，但没有任何东西是万无一失的。 11.8 局部敏感的散列算法 SHA还有一个重要特征，那就是局部不敏感的。 如果你修改其中的一个字符，再计算其散列值，结果将截然不同！[插图]这很好，让攻击者无法通过比较散列值是否类似来破解密码。 有时候，你希望结果相反，即希望散列函数是局部敏感的。 ❑ Google使用Simhash来判断网页是否已搜集。❑ 老师可以使用Simhash来判断学生的论文是否是从网上抄的。❑ Scribd允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容！这个网站可使用Simhash来检查上传的内容是否与小说《哈利·波特》类似，如果类似，就自动拒绝。 需要检查两项内容的相似程度时，Simhash很有用。 11.9 Diffie-Hellman密钥交换 这里有必要提一提Diffie-Hellman算法，它以优雅的方式解决了一个古老的问题：如何对消息进行加密，以便只有收件人才能看懂呢？ 在二战期间，德国人使用的加密算法比这复杂得多，但还是被破解了。Diffie-Hellman算法解决了如下两个问题。 ❑ 双方无需知道加密算法。他们不必会面协商要使用的加密算法。❑ 要破解加密的消息比登天还难。 Diffie-Hellman使用两个密钥：公钥和私钥。顾名思义，公钥就是公开的，可将其发布到网站上，通过电子邮件发送给朋友，或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥，就只有你才能解密消息！ 11.10 线性规划 最好的东西留到最后介绍。线性规划是我知道的最酷的算法之一。 线性规划是一个宽泛得多的框架，图问题只是其中的一个子集。但愿你听到这一点后心潮澎湃！ 11.11 结语 本章简要地介绍了10个算法，唯愿这让你知道还有很多地方等待你去探索。在我看来，最佳的学习方式是找到感兴趣的主题，然后一头扎进去，而本书便为你这样做打下了坚实的基础。