Как Вы отсортировали бы 1 миллион 32-разрядных целых чисел в 2 МБ RAM?
Я думаю, что это самый простой и лучший подход.
string str = "File_name,cost_per_page,0.23,color_code,343,thickness,0.01";
string[] array = str.Split(',');
Dictionary<string, double> dict = new Dictionary<string, double>();
for (int i = 1; i < array.Length - 1; i = i + 2)
{
string key = array[i];
double value = Double.Parse(array[i + 1], CultureInfo.InvariantCulture);
dict.Add(key, value);
}
Вы также можете использовать приведенный выше код для большей строки (переменная str имеет больше пар ключ-значение пар).
9 ответов
Необходимо предоставить больше информации. Какое дополнительное устройство хранения данных доступно? Где Вы, как предполагается, храните результат?
Иначе, самый общий ответ: 1. загрузите кулак половина данных в память (2 МБ), отсортируйте его по любому методу, произведите его в файл. 2. загрузите вторую половину данных в память (2 МБ), отсортируйте его по любому методу, сохраните его в памяти. 3. используйте алгоритм слияния, чтобы объединить две отсортированных половины и произвести полный отсортированный набор данных в файл.
1 миллион 32-разрядных целых чисел = 4 МБ памяти.
необходимо отсортировать их использующий некоторый алгоритм, который использует внешнее устройство хранения данных. Сортировка с объединением, например.
Этот статья Википедии о Внешней Сортировке имеют немного полезной информации.
Двойной вид турнира с полипоэтапным слиянием
#!/usr/bin/env python
import random
from sort import Pickle, Polyphase
nrecords = 1000000
available_memory = 2000000 # number of bytes
#NOTE: it doesn't count memory required by Python interpreter
record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
file_maker=Pickle,
verbose=True,
heap_size=heap_size,
max_files=4 * (nrecords / heap_size + 1))
# put records
maxel = 1000000000
for _ in xrange(nrecords):
p.put(random.randrange(maxel))
# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
if el > last: # elements must be in descending order
print "not sorted %d: %d %d" % (n, el ,last)
break
last = el
assert nrecords == (n + 1) # check all records read
- Гм, сохраните их всех в файле.
- Карта распределения памяти файл (Вы сказали, была только 2M RAM; давайте предположим, что адресное пространство является достаточно большим к карте распределения памяти файл).
- Отсортируйте их использующий запоминающее устройство файла, как будто это была реальная память теперь!
Никакой пример, но Блочная сортировка имеет относительно низкую сложность и достаточно легка реализовать
Поскольку люди выше упоминания вводят интервал 32 битов 4 МБ.
Для установки как можно большему количеству "Числа" в как можно меньшее количество пространства использование интервала типов, короткого и символ в C++. Вы могли быть ловкими (но иметь нечетный грязный код) путем выполнения нескольких типов кастинга для наполнения вещей везде.
Здесь это от края моего места.
что-либо, что является меньше, чем 2^8 (0 - 255), хранится как символ (1-байтовый тип данных)
что-либо, что является меньше, чем 2^16 (256 - 65535), и> 2^8 хранится как короткое (2-байтовый тип данных)
, Остальная часть значений была бы помещена в интервал (4-байтовый тип данных)
, Вы захотите определить, где символьный раздел запускается и заканчивается, где короткий раздел запускается и заканчивается, и где международный раздел запускается и заканчивается.
Разделите проблему на части, достаточно маленькие, чтобы вписаться в доступную память, затем использовать сортировка слиянием для объединения их.