Комикс: Как узнать, входит ли число в число 4 миллиардов целых чисел?

Статья из:www.iamshuaidi.com, веб-сайт программирования, посвященный набору в школу, собеседованиям и личным встречам.

Вопрос: у меня есть 4 миллиарда целых чисел, а затем я даю новое целое число, мне нужно определить, входит ли новое число в 4 миллиарда целых чисел, что бы вы сделали?

【Спросите Великого Бога】

Сяо Ши вернулся в школу и рассказал об интервью г-ну Лу из компьютерной школы.

Сяо Ши поспешно вытащил г-на Лу и спросил, почему интервьюер сказал, что это было слишком медленно, когда я сказал, что данные загружались 8 раз?

Учитель Лу: Ха-ха, загрузка данных с диска — это дисковая операция ввода-вывода, которая очень медленная. Вам приходится каждый раз загружать такое большое количество данных, и это занимает 8 раз. По моим оценкам, вам потребуется время, чтобы найти число. может достигать минут или даже часов.

Сяо Ши: Если бы это был ты, что бы ты сделал?

Преподаватель Лв: Вообще-то, интервьюер уже дал понять, он сказал, что даст вам партию машин, а это значит, что вы сможете использовать распределенные алгоритмы. Вы разбрасываете данные по 8 машинам, а потом приходите к новым данным, находите 8 машин вместе и, наконец, суммируете результаты.

Сяо Ши: Насколько это может быть быстрее?

Учитель Лу: Это должно быть в состоянии достичь второго уровня. Сяо Ши, ты можешь анализировать и анализировать сам.

Сяо Ши: Я думаю об этом... о, таким образом, поскольку каждая машина может одновременно считывать данные в память, вам не нужно загружать данные вперед и назад при сравнении, поэтому вы можете сохранить стоимость загрузки данных! Это действительно хороший способ.

【Лучшее решение】

Учитель Лу: На самом деле, это не лучший метод. У меня есть метод миллисекундного уровня. Хотите знать?

Сяо Ши: Конечно, хочу, научи меня.

Сяо Ши: О, да, так что я могу подать заявку на 4 миллиарда цифр, преобразовать новое число в одну цифру, а затем решить, является ли цифра 0 или 1.

Учитель Лу: Сяо Ши, вам нужно хорошенько подумать над проблемой.Если это 4 миллиарда цифр, какие из 4 миллиардов цифр 0, а какие 1? Пришло новое число, как судить, находится ли оно в пределах 4 миллиардов цифр?

Сяо Ши: Я думаю об этом, да, 4 миллиарда цифр, 4 миллиарда цифр, тогда каждая цифра равна 1, это. . .

Учитель Лу: На самом деле, вы можете подумать об этом.Диапазон 32-битного int составляет всего 2 в 32-й степени, что составляет около 4,2 миллиарда точек. Таким образом, вы можете подать заявку на 2 в 32-й степени.

Сяо Ши: Это означает, что я покрываю весь диапазон целых чисел, о, да. Таким образом, это можно сделать: 1 представляет первый бит, 2 представляет второй бит, а 2 в 32-й степени представляет последний бит. Среди 4 миллиардов чисел существующее число равно 1 в соответствующей позиции, а остальные биты равны 0.

Учитель Лу: Да, а как насчет нового числа?

Сяо Ши: Для нового числа ищите соответствующую цифру. Например, если приходит 1234, ищите цифру 1234. Если это 1, то оно существует, а если 0, то оно не существует.

Учитель Лу: Да, тогда сколько памяти нужно в этом случае?

Сяо Ши: Я думаю об этом, 2 в 32-й степени эквивалентно 2 в 29-й степени байта Вау, это всего 500 МБ, что действительно экономит много памяти.

Сяо Ши: Как вы придумали такой мощный алгоритм?

Учитель Лв: На самом деле, это очень известный алгоритм работы с большими данными, называемый методом растровых изображений, который по-английски называется bitmap. Как следует из названия, он использует биты для представления состояний, тем самым экономя место. У меня завтра занятие, я расскажу о растровом методе, можете прийти и послушать.

【Класс мистера Лу】

На следующий день г-н Лу начал занятия и выбросил вопросы интервью, с которыми Сяо Ши столкнулся в начале.

Преподаватель Лв: Студенты, это вопрос интервью от компании БАТ, у вас есть какие-нибудь идеи?

Как только голос стих, Брат Эгг встал, чтобы ответить. Брат Эгг — самый гордый ученик Учителя Лу, известный своим активным мышлением.

Эггман: Думаю, да. Прежде всего, диапазон 32-битных целых чисел составляет 4,2 миллиарда, и некоторые из этих 4 миллиардов целых чисел должны быть непрерывными.Мы можем сначала выполнить внешнюю сортировку данных, а затем использовать начальное число и длину для формирования данных структура для представления номера непрерывного периода, например.

Если данные 1 2 3 4 6 7..., они могут быть представлены (1, 4) и (6, 2), так что последовательные числа представлены двумя числами. После того, как приходит новое число, для его нахождения используется двоичный метод.

Таким образом, наихудший случай — это более 200 миллионов точек останова, то есть более 200 миллионов структур, каждая из которых составляет 8 байт, около 1,6 миллиарда байт и 1,6 ГБ, которые можно разместить в памяти.

Учитель Лу: Ну, очень хорошо, не только дал план, но и активно проанализировал пространство и возможности.

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

【После школы】

После занятий Сяо Ши снова нашла Учителя Лу.

Учитель Лу: Но ваши способности к пониманию все еще очень сильны. Вы можете понять многие вещи, как только услышите их. Это не то, что кто-либо может сделать.

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

Больше интервью в прямом эфире:

1. Как определить, входит ли число в число 4 миллиардов целых чисел?

2. Как реализовать стек, который может получить минимальное значение?

3. Помните собеседование с покупателем: оптимальное решение для наименьшего стека

4. Почему существует различие между стабильной и неустойчивой сортировкой?

5. Как запрограммировать решение проблемы Huarong Road?

6. Как найти самую длинную палиндромную подстроку в строке?

7. Как посчитать количество слов с определенным префиксом в 500w слова?

8. Как найти 1000 самых больших чисел из миллиарда чисел?

9. Как запрограммировать, чтобы в конце года получалось как можно больше красных конвертов?

10. Как программно решить проблему количества Моментов?

11. Как разработать самообучающийся ИИ Gobang?