3

Есть файл размером 1Гб который содержит FLOAT в бинарном виде, т.е. 4 байта на 1 значение. Как реализовать сортировку такого файла с применением многопоточности и с ограничением RAM 128mb и чтобы сложность алгоритма сортировки была приближена к O(2n)?

13
  • Сложности O(2n) не бывает. А по сути - пока забейте на многопоточность и попытайтесь хоть что-то сделать с ограничением памяти.
    – MBo
    2 ноя 2018 в 8:37
  • 2
    Самое то здесь - сортировка слиянием через файлы. Многопоточность в принципе может сыграть при сортировке разных частей, но только уже тогда, когда получаются файлы, полностью помещающиеся в память - иначе дисковые операции, скорее всего, просто сведут преимущества многопоточности на нет. Впрочем, все это надо пробовать и мерять...
    – Harry
    2 ноя 2018 в 8:48
  • 1
    Пока еще не придуман алгоритм сортировки, который бы гарантировал сложность меньше O(n*log(n)).
    – rjhdby
    2 ноя 2018 в 8:50
  • 1
    Попробуйте паралельно писать в много файлов (сколько открыть сможете), в каждый числа из определенного диапазона. В идеале бы получить объем каждого файла до 128Мб, но боюсь ограничение на количество открытых файлов все испортит. Плюс будут проблемы если распределение значений далеко от равномерного и из каких то диапазовов значений будет много больше, чем из других. Потребуется дополнительное дробление. Если файлы все таки получились, читаете их по порядку и сортируете значения внутри каждого из них.
    – Mike
    2 ноя 2018 в 9:18
  • 2
    rjhdby Это сортировка - подсчётом (counting sort). Только памяти немерено нужно.
    – MBo
    2 ноя 2018 в 9:33

1 ответ 1

2

Псевдокод

valueBytes = Float.bytes
input = new File(name = 'input')
counterBytes = minBytesToFit(ceil(input.size/valueBytes))

temp = CreateFile(name = 'temp', size = maxNumberFor(bytes = valueBytes)*counterBytes + counterBytes, fill = 0)
output = CreateFile(name = 'output', size = input.size)

for(i=0; input.size/valueBytes; i++){
    current=input.readNumber(offset = i*valueBytes, count = valueBytes)
    currentTemp = temp.readNumber(offset = current, count = counterBytes)
    currentTemp++
    temp.writeNumber(offset = current, count = counterBytes, value = currentTemp)
}

for(i=0; temp.size/counterBytes; i++){
    current = temp.readNumber(offset = i*counterBytes, count = counterBytes)
    out.append(value = i, count = current, blockSize = valueBytes)
}

PS Как заметил @MBo - это сортировка подсчетом. Только вместо памяти используется диск.

7
  • файл temp же должен быть 2^(Float.bytes * 8) - примерно 4.2Гб!
    – dgzargo
    2 ноя 2018 в 12:32
  • @dgzargo файл temp должен быть "максимальное значение" * "размер счетчика". Где максимальное значение - это 4 байта по FF, т.е. 0xFFFFFFFF, а размер счетчика - это количество байт, в которые гарантированно поместится число "размер файла"/"размер значения"
    – rjhdby
    2 ноя 2018 в 12:36
  • @dgzargo у меня вышло 15ГБ, хотя может где и облажался при расчете. Ну а что вы хотели при таких вводных? :) Зато сложность линейная и в заявленную память укладывается.
    – rjhdby
    2 ноя 2018 в 12:44
  • немного не ясно: "размер значения" == 4 байта по FF, т.е. 0xFFFFFFFF ?
    – dgzargo
    2 ноя 2018 в 12:56
  • @dgzargo по сути нам надо иметь ячейку счетчик для каждого возможного значения. т.е. от 0 до FFFFFFFF(длина значения 4 байта)
    – rjhdby
    2 ноя 2018 в 13:02

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.