在 C++ 中的向量中的每个索引处查找累积的唯一元素计数的有效方法

Question

所以我有一个基因比对结果（我认为它来自 RNA-seq），其中特定序列与某些基因相匹配（这些基因有时会自我重复）。我现在正在使用 C++ 查找最独特基因被计数的最早可能位置，我可以自信地只使用第一部分进行进一步分析。问题是我的文件已排序（因此来自同一基因的序列放在一起），但我想为未排序的文件计算它。

我现在正在做的是在遍历它之前手动 std::shuffle 我的 std::vector<string> geneList。在每次迭代中，我会将 geneList 中的每个即将到来的基因与一个独特的基因列表进行比较，如果其中的 none 匹配即将到来的基因，则更新它。然后我会以一定的间隔对 count_gene 和 count_unique_gene 进行采样，最后得到 x% 的位置。这是非常昂贵的……只有 140,000 个基因花了我几分钟的时间。示例代码（还包括我的输入代码以便更好地理解）：

#include <stdlib.h>
#include <stdint.h>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <fstream>
#include <sstream>
#include <random>
#include <algorithm>

class COUNT{

public:
//    COUNT() : sampRate(1) {};
//    ~COUNT(){};
    void initialize();
    void readData();
    void calcCount();
    void writeCount();

private:
    int sampRate;    
    int countRead;
    int countUniqGene;
    string fname;
    vector<string> geneList;
    vector<int> sampCountRead, sampCountUniqGene;
};


void COUNT::readData(){
    std::cout<<"Type in fname: "<<endl;
//    std::cin>>fname;
    fname = "testdata.sam";
    std::cout<<"Type in sample rate: "<<endl;
    std::cin>>sampRate;
    std::string line;
    std::fstream readFile(fname);
    while (getline(readFile, line)) {
        if (((char)line.back() == '-') | ((char)line.back() == '+')) {
            std::istringstream ss(line);
            std::string others, oriGeneName, realGeneName;
            ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others;
            if (ss >> others) {
                ss >> oriGeneName;
                realGeneName = oriGeneName.substr(5, oriGeneName.size());
                geneList.push_back(realGeneName);
            }
            else continue;
        }
        else continue;
    }
    readFile.close();
}

void COUNT::calcCount() {
    set<string> uniqGeneList = {"test"};
    auto rng = std::default_random_engine{};
    std::shuffle(std::begin(geneList), std::end(geneList), rng);  // this is fast (0.02s)
    vector<string>::iterator uniqIter;
    string geneName;
    for (vector<string>::iterator iter = geneList.begin(); iter != geneList.end(); ++iter) {  //this is very slow
        geneName = string(iter[0]);
        if (all_of(uniqGeneList.begin(), uniqGeneList.end(), [geneName](const std::string gene) {return geneName != gene; })) {
            uniqGeneList.insert(geneName);
            countUniqGene++;
        }
        countRead++;
        if (countRead % sampRate < 1) {
            sampCountRead.push_back(countRead);
            sampCountUniqGene.push_back(countUniqGene);
        }
    }
}

int main(){
    (not important, plotting and intersecting)
}

还有样本数据（我从 'GE:Z:<gene_name>' 项中提取了基因名）：

V300067289_HH26L1C001R0010008289    784 7   141178046   3   2S48M   *   0   0   CCCCACCTGCTTGCGGACCCTAATGTGACGTTGGCGGATGAGCACACGGG  F)BF;E2A3*F<+AFFB-B,FE?FEFFF@EF3BFB;<:FECEF2DFF@CE  NH:i:2  HI:i:1  AS:i:47 nM:i:0  CB:Z:53_34_81098_51183  UR:Z:GTTTTATTA  UY:Z:E/E@EAG?F
V300067289_HH26L1C001R0010008294    1040    3   34078775    255 50M *   0   0   CCTTGTCTGGGTGATTTAATAGCATAATCCGGCGATGAGCATCCCTGATC  FGFBGFFFDEGEBFEFBDFEEFFGCFFFADEEFGFFFFGFGFFDFFEEFF  NH:i:1  HI:i:1  AS:i:49 nM:i:0  CB:Z:49_31_75043_46832  UR:Z:CCGGACCCA  UY:Z:EEEFDBFEA  XF:Z:CODING GE:Z:Dnajc19    GS:Z:-
V300067289_HH26L1C001R0010008295    1040    3   34078777    255 2S48M   *   0   0   CGTTGTCTGGGTGATTTAATACCAAAATCCGGCGATGAGCATCCCTGATC  E(FC6D>+EDEFECA?@?:C.'D4&03@&;:3?7CFAEF@C7A4.4.@B?  NH:i:1  HI:i:1  AS:i:43 nM:i:2  CB:Z:49_31_75043_46832  UR:Z:CCGGACCCA  UY:Z:CFFD?EEDF  XF:Z:CODING GE:Z:Dnajc19    GS:Z:-
V300067289_HH26L1C001R0010008298    1040    15  82351046    255 50M *   0   0   ACTTTATCCCGTCCTTGTTTCACCGTGATATCCAGCTGCATTAAGTGCAC  )EFFF=FE?DC=FABGFFF7F&=FEF9FBEE=BEB9FFF;FFCF9DBF86  NH:i:1  HI:i:1  AS:i:49 nM:i:0  CB:Z:49_34_74093_51329  UR:Z:CAATATAGG  UY:Z:DFFFFFFFF  XF:Z:CODING GE:Z:Ndufa6 GS:Z:-

我想过假设基因外观服从泊松分布，只计算唯一基因数并计算在每个位置达到 x% 的置信度。但最好先使用模拟。提前致谢！

Answer 1

set<string> uniqGeneList = {"test"};

std::set 的全部目的是能够快速（如对数复杂度）检查是否存在特定值，该值是否存在于集合中。

    if (all_of(uniqGeneList.begin(), uniqGeneList.end(),
        [geneName](const std::string gene) {return geneName != gene; })) {

因此，与其让 std::set 准确地完成其存在的唯一目的，即发明它的唯一原因，不如手动地逐一迭代迭代中的每个值设置，然后手动比较呢？正如 Spock 先生所说：这不符合逻辑。

整个事情必须简单地替换为：

    if (uniqGeneList.find(geneName) == uniqGeneList.end()) {

粗略估计：集合中有大约一千个值，这最终用八个替换了一千个比较。通过将 std::set 替换为 std::unordered_set 也可以实现一些进一步的性能提升。您将需要对此进行概要分析，以查看这是否会成为您的用例的结果。

其他一些值得注意的事情：

        std::istringstream ss(line);
        std::string others, oriGeneName, realGeneName;
        ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others; ss >> others;

Streams 以低效着称。这也可能是牺牲太多电子的另一部分。在对性能敏感的情况下，放弃 std::istringstream，卷起袖子，遍历整行，在单词呼啸而过时对它们进行计数，也可能会挤出一些性能。

在 C++ 中的向量中的每个索引处查找累积的唯一元素计数的有效方法

Efficient way to find accumulated unique element count at each index in a vector in C++

c++

bioinformatics