Pertanyaan Need for Fast map antara string dan bilangan bulat


Saya memiliki peta string dan unsigned, di mana saya menyimpan kata ke frekuensinya bentuk berikut:

map<string,unsigned> mapWordFrequency; //contains 1 billion such mappings

Lalu saya membaca file besar (100GB), dan hanya menyimpan kata-kata dalam file yang memiliki frekuensi lebih besar dari 1000. Saya memeriksa frekuensi kata-kata dalam file menggunakan: mapWordFrequency [word]> 1000. Namun, ternyata mapWordFrequency saya memiliki 1 miliar pemetaan dan file saya sangat besar, oleh karena itu mencoba memeriksa mapWordFrequency [word]> 1000 untuk setiap kata dalam file sangat lambat dan membutuhkan waktu lebih dari 2 hari. Dapatkah seseorang menyarankan bagaimana saya dapat meningkatkan efisiensi kode di atas.

peta tidak sesuai dengan RAM saya dan swapping memakan banyak waktu.

Akankah menghapus semua kata yang memiliki frekuensi <1000 bantuan menggunakan fungsi hapus peta?


5
2017-09-01 06:48


asal


Jawaban:


Saya sarankan Anda menggunakan unordered_map sebagai lawan dari map. Seperti yang sudah dibahas dalam komentar, yang pertama akan memberi Anda waktu penyisipan / pengambilan O(1) sebagai lawan O(logn) di sebuah map.

Seperti yang Anda katakan, memori swapping memakan banyak waktu. Jadi bagaimana mengatasi masalah secara bertahap. Muat data maksimum dan unordered_map Anda dapat masuk ke memori, hash, dan melanjutkan. Setelah satu kali berlalu, Anda harus memiliki banyak unordered_maps, dan Anda dapat mulai menggabungkannya dalam laluan berikutnya.

Anda dapat meningkatkan kecepatan dengan melakukan ini secara terdistribusi. Memproses potongan-potongan data di komputer yang berbeda, dan kemudian menggabungkan data (yang akan berupa peta tidak berurutan. Namun, saya tidak memiliki pengalaman sebelumnya dalam komputasi terdistribusi, dan jadi tidak dapat membantu di luar ini.

Juga, jika menerapkan sesuatu seperti ini terlalu rumit, saya sarankan Anda menggunakan mergesort eksternal. Ini adalah metode penyortiran file yang terlalu besar untuk masuk ke dalam memori dengan menyortir potongan yang lebih kecil dan menggabungkannya. Alasan saya menyarankan ini adalah bahwa mergesort eksternal adalah teknik yang cukup umum, dan Anda mungkin menemukan solusi yang sudah diterapkan untuk kebutuhan Anda. Meskipun kompleksitas waktu penyortiran lebih tinggi dari ide Anda menggunakan map, itu akan mengurangi overhead swapping jika dibandingkan dengan peta. Seperti yang ditunjukkan dalam komentar, sort di linux mengimplementasikan mergesort eksternal.


4
2017-09-01 07:05



Anda dapat menggunakan peta hash di mana string hash Anda akan menjadi kunci dan kejadian akan menjadi nilai. Ini akan lebih cepat. Anda dapat memilih hashing string yang bagus berdasarkan kebutuhan Anda. Berikut ini tautan beberapa fungsi hashing yang bagus:

http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

Anda dapat menggunakan beberapa perpustakaan pihak ketiga untuk ini juga.

EDIT: kode semu

int mapWordFrequency[MAX_SIZE] = {0} ;// if MAX_SIZE is large go with dynamic memory location
int someHashMethod(string input);

loop: currString in ListOfString
          int key = someHashMethod(currString);
          ++mapWordFrequency[key];
          if(mapWordFrequency[key] > 1000)
              doSomeThing();

Memperbarui: Seperti yang ditunjukkan @Jens ada beberapa kasus ketika someHashMethod () akan mengembalikan int yang sama (hash) untuk dua string yang berbeda. Dalam hal ini kita harus menyelesaikan tabrakan dan kemudian waktu pencarian akan lebih dari konstan. Juga karena ukuran masukan sangat besar membuat larik tunggal dari ukuran itu mungkin tidak dapat dilakukan. Dalam hal ini kita dapat menggunakan konsep komputasi terdistribusi tetapi waktu pencarian yang sebenarnya akan kembali naik dibandingkan dengan mesin tunggal.


2
2017-09-01 06:56



Tergantung pada distribusi statistik kata-kata Anda, mungkin perlu dikompresi setiap kata sebelum menambahkannya ke peta. Selama ini adalah kompresi tanpa kehilangan Anda dapat memulihkan kata-kata asli setelah penyaringan. Idenya adalah Anda mungkin dapat mengurangi ukuran kata rata-rata (maka menghemat memori, dan waktu membandingkan kunci). Berikut ini adalah prosedur kompresi / dekompresi sederhana yang dapat Anda gunakan:

#include <string>
#include <sstream>
#include <boost/iostreams/filtering_streambuf.hpp>
#include <boost/iostreams/filter/zlib.hpp>
#include <boost/iostreams/copy.hpp> 

inline std::string compress(const std::string& data)
{
    std::stringstream decompressed {data};
    boost::iostreams::filtering_streambuf<boost::iostreams::input> stream;
    stream.push(boost::iostreams::zlib_compressor());
    stream.push(decompressed);
    std::stringstream compressed {};
    boost::iostreams::copy(stream, compressed);
    return compressed.str();
}

inline std::string decompress(const std::string& data)
{
    std::stringstream compressed {data};
    boost::iostreams::filtering_streambuf<boost::iostreams::input> stream;
    stream.push(boost::iostreams::zlib_decompressor());
    stream.push(compressed);
    std::stringstream decompressed;
    boost::iostreams::copy(stream, decompressed);
    return decompressed.str();
}

Selain menggunakan std::unordered_map seperti yang disarankan orang lain, Anda juga bisa memindahkan kata-kata yang sudah dilihat lebih dari 1000 kali dari peta, dan menjadi std::unordered_set. Ini juga perlu memeriksa set sebelum peta, tetapi Anda mungkin melihat kinerja hash yang lebih baik dengan melakukan hal ini. Mungkin juga perlu dilakukan pengulangan ulang jika Anda menggunakan strategi ini.


1
2017-09-01 08:07



Anda perlu pendekatan lain untuk masalah Anda, data Anda terlalu besar untuk diproses sekaligus. Misalnya Anda dapat membagi file Anda menjadi beberapa file, katakanlah yang paling mudah adalah secara logis membaginya dengan huruf.

100GB/24 letters = 4.17 GB

Sekarang Anda akan memilikinya 24 file dari 4.17GB setiap. Anda tahu bahwa kata-kata di salah satu file tidak dapat menjadi bagian dari file lain, ini akan membantu Anda, karena Anda tidak perlu menggabungkan hasilnya. Dengan file 4GB, sekarang menjadi lebih mudah untuk bekerja di ram.

std::map memiliki masalah ketika Anda mulai menggunakan banyak memori, karena fragmennya banyak. Mencoba std::unordered_map, dan jika itu masih tidak berkinerja baik, Anda mungkin dapat memuat di memori file dan mengurutkannya. Menghitung kejadian akan sangat mudah.

Dengan asumsi Anda memiliki beberapa duplikat, Anda map atau unordered_map akan memiliki jejak memori yang secara signifikan lebih rendah.

Jalankan kode Anda dalam satu lingkaran, untuk setiap file, dan tambahkan hasilnya di file lain. Anda harus melakukannya dengan sangat cepat.


1
2017-09-01 08:17



Masalah utama tampaknya adalah jejak memori, jadi kami mencari solusi yang menggunakan sedikit memori. Cara untuk menghemat memori adalah dengan menggunakan diurutkan vectors bukannya map. Sekarang, vector memiliki waktu pencarian dengan ~ log (n) perbandingan dan waktu insert rata-rata n / 2, yang buruk. Keuntungannya adalah Anda pada dasarnya tidak memiliki overhead memori, memori yang akan dipindahkan kecil karena pemisahan data dan Anda mendapatkan memori sekuensial (cache-keramahan) yang dapat dengan mudah mengungguli map. Memori yang diperlukan adalah 2 (wordcount) + 4 (indeks) + 1 (\0-char) + x (panjang kata) byte per kata. Untuk mencapai itu kita perlu menyingkirkannya std::string, karena terlalu besar dalam hal ini.

Anda dapat membagi Anda map menjadi vector<char> yang menyimpan string satu demi satu dipisahkan oleh \0-karakter, a vector<unsigned int> untuk indeks dan a vector<short int> untuk jumlah kata. Kode akan terlihat seperti ini (diuji):

#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <fstream>
#include <iostream>

std::vector<char> strings;
std::vector<unsigned int> indexes;
std::vector<short int> wordcount;
const int countlimit = 1000;

void insertWord(const std::string &str) {
    //find the word
    auto stringfinder = [](unsigned int lhs, const std::string &rhs) {
        return &strings[lhs] < rhs;
    };
    auto index = lower_bound(begin(indexes), end(indexes), str, stringfinder);
    //increment counter
    if (index == end(indexes) || strcmp(&strings[*index], str.c_str())) { //unknown word
        wordcount.insert(begin(wordcount) + (index - begin(indexes)), 1);
        indexes.insert(index, strings.size());
        strings.insert(end(strings), str.c_str(), str.c_str() + str.size() + 1);
    }
    else { //known word
        auto &count = wordcount[index - begin(indexes)];
        if (count < countlimit) //prevent overflow
            count++;
    }
}

int main() {
    std::ifstream f("input.txt");
    std::string s;
    while (f >> s) { //not a good way to read in words
        insertWord(s);
    }
    for (size_t i = 0; i < indexes.size(); ++i) {
        if (wordcount[i] > countlimit) {
            std::cout << &strings[indexes[i]] << ": " << wordcount[i] << '\n';
        }
    }
}

Pendekatan ini masih menyimpan semua kata dalam memori. Menurut Wolfram Alpha panjang kata rata-rata dalam bahasa Inggris adalah 5,1 karakter. Ini memberi Anda kebutuhan memori total (5.1 + 7) * 1bn bytes = 12.1bn bytes = 12.1GB. Dengan asumsi Anda memiliki komputer modern setengah dengan 16 + GB RAM Anda dapat memasukkan semuanya ke dalam RAM.

Jika ini gagal (karena Anda tidak memiliki kata-kata bahasa Inggris dan mereka tidak cocok dalam memori), pendekatan selanjutnya adalah file yang dipetakan memori. Dengan cara itu Anda bisa membuatnya indexes arahkan ke file yang dipetakan memori, bukan strings, sehingga Anda dapat menyingkirkannya strings, tetapi waktu akses akan menderita.

Jika ini gagal karena kinerja rendah Anda harus melihat ke dalam peta-mengurangi yang sangat mudah diterapkan pada kasus ini. Ini memberi Anda kinerja sebanyak Anda memiliki komputer.


1
2017-09-01 09:51



@TonyD Bisakah Anda memberikan contoh kecil dengan trie? - Rose Sharma

Berikut ini contoh pendekatan trie untuk masalah ini:

#include <iostream>
#include <string>
#include <limits>
#include <array>

class trie
{
  public:
    void insert(const std::string& s)
    {
        node_.insert(s.c_str());
    }

    friend std::ostream& operator<<(std::ostream& os, const trie& t)
    {
        return os << t.node_;
    }

  private:
    struct Node
    {
        Node() : freq_(0) { }
        uint16_t freq_;
        std::array<Node*, 26> next_letter_{};

        void insert(const char* p)
        {
            if (*p)
            {
                Node*& p_node = next_letter_[*p - 'a'];
                if (!p_node)
                    p_node = new Node;
                p_node->insert(++p);
            }
            else
                if (freq_ < std::numeric_limits<decltype(freq_)>::max()) ++freq_;
        }
    } node_;

    friend std::ostream& operator<<(std::ostream& os, const Node& n)
    {
        os << '(';
        if (n.freq_) os << n.freq_ << ' ';
        for (size_t i = 0; i < 26; ++i)
            if (n.next_letter_[i])
                os << char('a' + i) << *(n.next_letter_[i]);
        return os << ')';
    }
};

int main()
{
    trie my_trie;
    my_trie.insert("abc");
    my_trie.insert("abcd");
    my_trie.insert("abc");
    my_trie.insert("bc");
    std::cout << my_trie << '\n';
}

Keluaran:

(a(b(c(2 d(1 ))))b(c(1 )))

Outputnya berupa representasi histogram kata-frekuensi terkompresi / seperti pohon: abc muncul 2 waktu, abcd  1, bc  1. Tanda kurung dapat dianggap sebagai mendorong dan memunculkan karakter dari "tumpukan" untuk membentuk awalan saat ini atau - ketika ada kata nomor.

Apakah itu meningkatkan banyak hal di peta tergantung pada variasi dalam kata-kata masukan, tapi itu patut dicoba. Implementasi yang lebih efisien memori mungkin menggunakan vector atau set - atau bahkan a string katakanlah sufiks dipisahkan-ruang ketika ada beberapa elemen di bawah awalan saat ini, kemudian beralih ke array-of-26-pointers ketika itu cenderung membutuhkan lebih sedikit memori.


1
2017-09-01 10:29