Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.95
Butt-Head
Заблокирован
#1

Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти - C++

29.07.2015, 16:30. Просмотров 3457. Ответов 85
Метки нет (Все метки)

Привет!
Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1 террабайт, если на компе, к примеру, доступно всего 2 гб оперативки ... ?
Ну файл с нитами типа:
1
2
3
4
6346546
234524234
656546546
24234234
777
654646
и тд



Добавлено через 1 час 11 минут
Важная тема теряется... Up!

Добавлено через 4 часа 45 минут
Ну так что, никто не подскажет, как отсортировать 1 гиг в файле?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2015, 16:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти (C++):

Наиболее быстрый способ сравнения двух экземпляров структур на предмет одинаковости их полей - C++
Есть структура, в которой есть несколько int-ов и char-ов, какой имеется наиболее быстрый способ в C/C++ для сравнения двух экземпляров...

Memory shift или самый быстрый способ перемещения блока памяти - C++
int* dataField = new int{0}; for (int i = 0; i < 50; i++) dataField = 777; //тут должен быть memory shift delete dataField;...

Работа с бинарными файлами: какой способ работает наиболее быстро при записи и считывании? - C++
Всем привет прошу помощи по этой теме. Попробую изложить кратко: 1) Есть не бинарный файл -> Считываю его ifstream -> работаю с данными...

Быстрый способ получение уникального ID - C++
Есть какой - то список уже существующих уникальных ID, нужно наибыстрейшим способом создать новый уникальный для этого списка ID. (пусть...

Самый быстрый способ решения задачи a+b - C++
несколько раз ходил на олимпиады, во многих из них в пробном туре даётся задача а+б, решаю её стандартным способом: cin >> a >> b; ...

Быстрый способ сравнить содержимое двух файлов - C++
Здравствуйте, подскажите наиболее быстрый способ сравнить содержимое двух текстовых файлов и вывести различия.

85
ct0r
Игогошка!
1776 / 678 / 42
Регистрация: 19.08.2012
Сообщений: 1,292
Завершенные тесты: 1
30.07.2015, 14:06 #46
Считали 3 55. Отсортировали. Записали 3 55 в файл 1.dump
Считали 24 2. Отсортировали. Записали 2 24 в 2.dump
Считали 3 2. Отсортировали. Записали 2 3 в 3.dump

Итого у нас 3 открытых файла
3 55
2 24
2 3

Считываем например по одному значению из них - 3 2 2. Берем минимальное - 2, пишем в выходной файл его, считываем из файла, откуда мы взяли эту двойку, следующее число - 24. Выбираем минимальное из 3 24 2. Это 2. Пишем в выходной файл. Читаем из третьего файла (посколько мы оттуда уже взяли двойку и записали в выходной файл) тройку. Берем минимум из 3 24 3. И так далее.

Я показал пример без буферов чтения отсортированных кусков, чтобы идея была понятнее.

Цитата Сообщение от Butt-Head Посмотреть сообщение
Так ты сейчас в Янедксе работаешь или уже откинулся ?
Сейчас не в яндексе, а в его конкуренте

Цитата Сообщение от Butt-Head Посмотреть сообщение
Это задача тех, кто занимается подобными вещами.
Это была моя первая работа. О каких подобных вещах ты говоришь? Тут нет никакой специфики, должен каждый уметь.
1
Butt-Head
Заблокирован
30.07.2015, 14:15  [ТС] #47
Цитата Сообщение от ct0r Посмотреть сообщение
Берем минимальное - 2, пишем в выходной файл его, считываем из файла, откуда мы взяли эту двойку, следующее число - 24.
Всё. Теперь идею понял. Спасибо.
Eraston, ты нуб, объяснять ваще не умеешь Но всё равно спасибо

Цитата Сообщение от ct0r Посмотреть сообщение
Сейчас не в яндексе, а в его конкуренте
в гугле что ли?
Цитата Сообщение от ct0r Посмотреть сообщение
О каких подобных вещах ты говоришь? Тут нет никакой специфики, должен каждый уметь.
Каждый должен знать то, что ему нужно знать в текущей момент времени, а так же владеть информацией о том, где посмотреть дополнительную информацию для решения других задач. Иначе ты просто загрузишь себе череп всякой хренатенью алгоритмической и на то, что б свободно мыслить и решать творческие задачи у тебя не хватит оперативки в мозгу. Поверь мне, я знаю что говорю. Слышал историю про маленьких гениев? Один из них в 8 или 9 лет мог "брать 4-х этажные интегралы", но не мог даже себе жопу самостоятельно подтереть, т.к. всё время забывал, как это делается.
0
Eraston
30.07.2015, 14:20
  #48

Не по теме:

Цитата Сообщение от Butt-Head Посмотреть сообщение
Eraston, ты нуб, объяснять ваще не умеешь
Уровень понимания не зависит от уровня объяснения ©.

0
Butt-Head
Заблокирован
30.07.2015, 14:23  [ТС] #49
Цитата Сообщение от Eraston Посмотреть сообщение
Уровень понимания не зависит от уровня объяснения ©.
Пфффф.... Ты лунтик что ли?
0
ct0r
Игогошка!
1776 / 678 / 42
Регистрация: 19.08.2012
Сообщений: 1,292
Завершенные тесты: 1
30.07.2015, 14:29 #50
Цитата Сообщение от Butt-Head Посмотреть сообщение
Каждый должен знать то, что ему нужно знать в текущей момент времени, а так же владеть информацией о том, где посмотреть дополнительную информацию для решения других задач.
Ну смотри. Тебе нужно отсортировать много-много чисел. Ты вроде как знаешь - быстрая сортировка и норм. И из-за незнания того, что существуют специальные более быстрые методы сортировки именно для целых чисел, ты реализуешь не самый эффективный алгоритм. Конечно, подробно все заучивать не надо, действительно перегрузишься, но общее поверхностное представление - что вообще существует и когда что лучше применять - нужно иметь по многим вопросам.
1
Butt-Head
Заблокирован
30.07.2015, 14:39  [ТС] #51
Цитата Сообщение от ct0r Посмотреть сообщение
но общее поверхностное представление - что вообще существует
Вот этого и достаточно.
Цитата Сообщение от ct0r Посмотреть сообщение
Ты вроде как знаешь - быстрая сортировка и норм. И из-за незнания того
Почему же. Перед решением ответственной задачи я загляну в гугл и он отправит меня на хабр, стековерфлоу или сюда, где собственно я и узнаю о наилучшем методе сортировке в данном конкретном случае.
Видишь, даже мой тред называется: "Наиболее быстрый способ сортировки файла...". Я зашёл сюда, что бы узнать..
У человечества всё больше и больше знаний и забивать голову всякой ерундой, которую можно посмотреть на любом форуме, не имеет никакого смысла, собственно как и оценивать кандидата на собеседование аналогичными задачами. Сейчас более эффективна ссылочная память, то есть помнишь, что такое есть, примерное где применяется и главное, где посмотреть. Так больше в голову влезает
По этому я и говорил:
Цитата Сообщение от Butt-Head Посмотреть сообщение
а так же владеть информацией о том, где посмотреть дополнительную информацию для решения других задач.
Правда конечно же, в случае глобального катаклизма и краха интернета с одновременным уничтожением всех физических архивов каким - нибуть астероидом или ядреной войной, человечество быстро откатится до уровня каменного века, что собственно скорее всего уже было и не раз.
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.07.2015, 15:00 #52
Цитата Сообщение от Butt-Head Посмотреть сообщение
У человечества всё больше и больше знаний и забивать голову всякой ерундой
Ну, для программиста основы структур данных и алгоритмов - это, по сути, таблица умножения.
0
shmkv
602 / 316 / 41
Регистрация: 21.07.2015
Сообщений: 912
30.07.2015, 15:01 #53
Цитата Сообщение от ct0r Посмотреть сообщение
Впрочем облегчу тебе задачу - раз мы суммарно в них записали 1 Тб
Это как? С каких пор сортировка слиянием стала работать за O(N)?
И вообще я сильно сомневаюсь, что сортировка слиянием тут будет быстрее.
0
w e
0 / 0 / 0
Регистрация: 10.03.2014
Сообщений: 15
30.07.2015, 15:02 #54
Цитата Сообщение от ct0r Посмотреть сообщение
можем сортировать за O(n)
смешно)
а почему через жесткий диск не попробовать?
0
shmkv
602 / 316 / 41
Регистрация: 21.07.2015
Сообщений: 912
30.07.2015, 15:07 #55
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, для программиста основы структур данных и алгоритмов - это, по сути, таблица умножения.
Смотря чем этот программист будет заниматься...

Добавлено через 4 минуты
Вот есть последовательность 3 1 4 1 5 9
на первом этапе мы записали 13 14 59 и все, памяти уже переписано эквивалентно исходной последовательности, а она еще не отсортирована. В чем я не прав?
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.07.2015, 15:13 #56
Цитата Сообщение от shmkv Посмотреть сообщение
Смотря чем этот программист будет заниматься...
Попробую угадать с трех раз. Хранением и обработкой данных с помощью алгоритмов?
0
shmkv
30.07.2015, 15:20
  #57

Не по теме:

Цитата Сообщение от Mr.X Посмотреть сообщение
Хранением и обработкой данных с помощью алгоритмов?
Если бы... У нас очень много вакансий для "программистов", где по факту человеку предстоит знаться другими вещами.

0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.07.2015, 15:23 #58
Цитата Сообщение от shmkv Посмотреть сообщение
Если бы... У нас очень много вакансий "программистов", где по факту человеку предстоит знаться другими вещами.
Ну так это и не программисты, а специалисты по другим вещам. Здесь же все типа программисты.
0
Butt-Head
Заблокирован
30.07.2015, 15:26  [ТС] #59
Цитата Сообщение от shmkv Посмотреть сообщение
на первом этапе мы записали 13 14 59 и все, памяти уже переписано эквивалентно исходной последовательности
не очень понял суть вопроса...
Да, ты сделал три блока, отсортированных локально как бы, то есть внутри себя и записал их в файлы.
Далее открываешь одновременно все эти файлы, в данном случае с 13, 14 и 59 и читаешь из них (из каждого), первое значение, получается:
1
1
5
ищешь первое минимальное, - это один из первого файла, пишешь это значение (единицу) в результирующий файл и cдвигаешь ленту первого файла на одно значение и берёшь опять слепок ;)
Смари, тут просто хитрость, представь тре плёнки от фотоаппарата (ну раньше были плёночные фотоаппараты, в курсе? :D ) Вот ты кладёшь их на стол. Берёшь... ну не знаю, листочек А4 и вырезаешь прямоугольник в нём, что б в столбик там поместилось 3 слайда. Кладёшь этот листок на три плёнки свои на столе на начало плёнок. Видишь там в столбик три кадра в столбик (по кадру от каждой плёнке) (первые кадры), это как бы три значения. Ищешь минимальное значение и записываешь его в результирующий файл. После этого, ты рукой сдвигаешь ленту с кадрами, с которой ты "брал" кадр, влево на 1 кадр и смотришь опять в прямоугольное окно... и т.д.

Добавлено через 1 минуту
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну так это и не программисты, а специалисты по другим вещам. Здесь же все типа программисты.
Алгоритмы и структуры данных требуются в 3..5 % вакансий программистов С++
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.07.2015, 15:28 #60
Цитата Сообщение от Butt-Head Посмотреть сообщение
Алгоритмы и структуры данных требуются в 3..5 % вакансий программистов С++
В смысле? Если вы код пишете, то они вам требуются, а если нет, то это вроде и не программирование.
0
30.07.2015, 15:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2015, 15:28
Привет! Вот еще темы с ответами:

Быстрый способ определения цвета пиксела координатам x, y - C++
В общем задача такая , нужен быстрый способ определения цвета пиксела в настоящее время на экране по заданным координатам x, y мне нужно...

Наиболее быстрый способ склеивания фрагментов файла - C#
Имеется несколько фрагментов одного файла. Требуется собрать эти фрагменты в исходный файл. Размеры фрагментов могут быть разными, от...

Наиболее быстрый способ забрать данные из html - C# ASP.NET
Мне нужно забрать данные с вебстранички. Там может содержаться просто одно слово, например "ОК", в этом случае использую следующую...

Наиболее быстрый способ работы с файлом Excel (около 20000 строк) - C#
Здравствуйте ребята, хотел спросить у вас совета. Есть программа по распечатке ценников по артикулу или штрихкоду товара. Какой обработкой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru