Как вы сортируете словарь по его значениям, а затем суммируете эти значения до определенной точки? - PullRequest
Новая
       3

Как вы сортируете словарь по его значениям, а затем суммируете эти значения до определенной точки?

0 голосов
/ 16 ноября 2018

Мне было интересно, как лучше всего отсортировать словарь типа Dict {String, Int} на основе значения. Я зацикливаюсь на файле FASTQ, содержащем несколько записей последовательности, каждая запись имеет строку в качестве идентификатора, которая служит ключом, и другую строку, в которой я беру длину в качестве значения ключа.

например: 

    testdict["ee0a"]=length("aatcg")
    testdict["002e4"]=length("aatcgtga")
    testdict["12-f9"]=length(aatcgtgacgtga")

В этом случае пары значений ключа будут "ee0a" => 5, "002e4" => 8 и "12-f9" => 13.

То, что я хочу сделать, это отсортировать эти пары от наивысшего значения до наименьшего значения, после чего я суммирую эти значения в другом, пока эта переменная не пройдет определенный порог. Затем мне нужно сохранить ключи, которые я использовал, чтобы я мог использовать их позже.

Можно ли использовать функцию sort () или использовать SortedDict для достижения этой цели? Я мог бы представить, что если сортировка прошла успешно, я мог бы использовать цикл while, чтобы добавить свои ключи в список и добавить мои значения в другую переменную, пока он не превысит мой порог, а затем использовать список ключей, чтобы создать новый словарь с моим выбранные пары ключ-значение.

Однако какой самый быстрый способ сделать это? файлы FASTQ, которые я читаю, могут содержать данные объемом в несколько ГБ, поэтому я хотел бы создать отсортированный словарь при чтении в файле и выбрать нужные записи, прежде чем делать что-либо еще с данными.

Ответы [ 2 ]

0 голосов
/ 17 ноября 2018

Если у вас достаточно памяти для хранения хотя бы одного или двух полных Dict необходимого размера, вы можете использовать инвертированный Dict с длиной в качестве ключа и массив старых ключей в качестве значений, чтобы избежать потери данных с дубликатом значение длины в качестве того же ключа.

Я думаю, что приведенный ниже код - это то, к чему ведет ваш вопрос: 

d1 = Dict("a" => 1, "b" => 2, "c" => 3, "d" => 2, "e" => 1, "f" =>5)

d2 = Dict()
for (k, v) in d1
    d2[v] = haskey(d2, v) ? push!(d2[v], k) : [k]
end

println(d1)
println(d2)

for k in sort(collect(keys(d2)))
    print("$k, $(d2[k]);  ")
    # here can delete keys under a threshold to speed further processing
end

Если у вас недостаточно памяти для хранения всего Dict, вы можете воспользоваться сначала поместить данные в базу данных SQL, такую ​​как SQLite, а затем делать запросы вместо изменения Dict в памяти. В этом случае один столбец таблицы будут данные, и вы добавите столбец для длины данных в таблицу SQLite. Или вы можете использовать PriorityQueue, как в ответе выше.

0 голосов
/ 16 ноября 2018

Если ваш файл имеет данные на несколько ГБ, я бы не стал хранить их в Dict. Я думаю, что лучше обрабатывать файл последовательно и хранить ключи, которые соответствуют вашему условию, в PriorityQueue из пакета DataStructures.jl. Конечно, вы можете повторить ту же процедуру, если вы читаете данные из словаря в памяти (просто изменяется источник из файла на диске в словарь)

Вот псевдокод того, что вы могли бы рассмотреть (полное решение будет зависеть от того, как вы читаете свои данные, которые вы не указали). Предположим, что вы хотите хранить элементы до тех пор, пока они не превысят пороговое значение, сохраняемое в константе THRESH. 

pq = PriorityQueue{String, Int}()
s = 0

while (there are more key-value pairs in source file)
    key, value = read(source file)
    # this check avoids adding a key-value pair for which we are sure that
    # it is not interesting
    if s <= THRESH || value > peek(pq)[2]
        enqueue!(pq, key, value)
        s += value
        # if we added something to the queue we have to check
        # if we should not drop smallest elements from it
        while s - peek(pq)[2] > THRESH
            s -= dequeue!(pq)[2]
        end
    end
end

После этого процесса pq будет содержать только те пары ключ-значение, которые вас интересуют. Основное преимущество этого подхода заключается в том, что вам никогда не нужно хранить все данные в ОЗУ. В любой момент времени вы сохраняете только те пары ключ-значение, которые были бы выбраны на данном этапе обработки данных.

Обратите внимание, что этот процесс не дает легко предсказуемого результата, поскольку несколько ключей могут иметь одинаковое значение. И если это значение будет находиться на границе отсечения, вы не знаете, какие из них будут сохранены (однако вы не указали, что вы хотите сделать в этом особом случае - если вы указали бы требование для этого случая, алгоритм должен быть обновлен немного).

...