优化大数组的反转计数(即对于 i<j，a[i]>a[j]) [英] optimising count of inversion(i.e for i&lt;j, a[i]&gt;a[j]) for a large array

问题描述

我正在尝试计算倒数(例如，对于数组 [2,5,4,1] 倒数是 = 4 即 (2,1),(5,4),(5,1),(4,1) 对一大组数组使用分而治之，当一个函数执行每个合并排序时，我得到一个递归计数.我将所有计数值存储在一个向量中，然后再次使用求和运算，它适用于 70,000 的数组大小，但之后失败.我觉得我不必要地将一个大值存储到 vector，相反，我正在寻找一种方法来直接计算相同，但我没有办法做到这一点，请帮助我实现它.

I am trying to count inversion(for eg.,for array [2,5,4,1] the inversion count is=4 namely (2,1),(5,4),(5,1),(4,1) using divide and conquer for a large set of arrays, I am getting a recursive count of value when a function executes each merge sort. I store all the count values in a vector and then again use sum operations, it works well for an array size of 70,000 but fails after it. I feel I am unnecessarily storing a large value to vector, instead, I am looking for a way to directly count the same but I am not getting a way to do the same, please help me in achieving it.

PS:文件链接是这个.我的代码看起来像;

ps:the file link is this. my code looks like;

#include<iostream>
#include<vector>
#include<fstream>
using namespace std;
long long greater_v(long long *array,long long ap,long long p){
    long long numx=0;
    for(long long i=0;i<p;i++){
        if(array[i]>ap){
            numx++;
        }
    }
    return numx;
}
long long merge(long long U[],long long Lu,long long V[],long long Lv,long long S[],long long count1){
    long long uf=0;long long vf=0;
    for(long long sb=0;sb<Lu+Lv;sb++){
        if(uf<Lu && vf<Lv){
            if(U[uf]<V[vf]){
                S[sb]=U[uf];uf++;}
            else{
                S[sb]=V[vf];
               count1=count1+=greater_v(U,V[vf],Lu);
                
                vf++;
                

            }
        }
        else if(uf<Lu){
            S[sb]=U[uf];uf++;
        }
        else{
            S[sb]=V[vf];vf++;
        }
    }
return count1;
}

在这部分中，我正在寻找将值存储在向量中的帮助，相反，我想要一种直接计数的方法.

In this part I am looking for help where I am storing the value in the vector, instead, i want a way to directly count.

vector<unsigned long long int>v_val;
void MergeSort(long long arr[],long long n){
    long long count=0;
    //cout<<"sorting  ";print(arr,n);
    if(n==1)
        return;
    long long U[n/2];long long V[n-n/2];
    for(long long i=0;i<n/2;i++){
        U[i]=arr[i];
        }
    for(long long i=0;i<n-n/2;i++){
        V[i]=arr[i+n/2];
        }
    MergeSort(U,n/2);
    MergeSort(V,n-n/2);
    count+=merge(U,n/2,V,n-n/2,arr,count);
    v_val.push_back(count);
}

主要功能是;

int main(){
long long test_count=0;
    ifstream file_num("pr_as_2.txt");
    long long arr_num[100000];
    for(long long i=0;i<100000;i++){
        file_num>>arr_num[i];
    }


unsigned long long int sum_val=0;
   MergeSort(arr_num,70000);
   for(size_t i=0;i<v_val.size();i++){
       sum_val+=v_val[i];
   }
   cout<<sum_val;

}

推荐答案

看看这个方法，它对我有用.

look at this approach, it worked for me.

#include <bits/stdc++.h>

using namespace std;

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
unsigned int merge(int arr[], int temp[], int l, int m, int r) {
    unsigned int inversions = 0;
    int i = l;
    int j = m;
    int k = l;
    while (i < m && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
            inversions += m-i;
        }
        k++;
    }
    while (i < m) {
        temp[k] = arr[i];
        i++;
        k++;
    }
    while (j <= r) {
        temp[k] = arr[j];
        j++;
        k++;
    }
    for (int i = l; i <= r; i++) {
        arr[i] = temp[i];
    }
    return inversions;
}

unsigned int count(int arr[], int temp[], int l, int r) {
    unsigned int inversions = 0;
    if (r > l) {
        int m = (r+l)/2;
        inversions = count(arr, temp, l, m);
        inversions += count(arr, temp, m+1, r);
        inversions += merge(arr, temp, l, m+1, r);
    }
    return inversions;
}

int main() {
    int arr_size = 100000;
    int arr[arr_size];
    ifstream file("IntegerArray.txt");
    string str;
    int i = 0;
    while (getline(file, str)) {
        arr[i] = stoi(str);
        i++;
    }
    // int arr[] = { 1, 20, 6, 4, 5 };
    // int arr_size = sizeof(arr) / sizeof(arr[0]);
    int temp[arr_size];
    /* mergeSort(arr, 0, arr_size-1);
    for (int i = 0; i < arr_size; i++) {
        cout << arr[i] << " ";
    } */
    cout << count(arr, temp, 0, arr_size-1) << endl;
}

这篇关于优化大数组的反转计数(即对于 i<j，a[i]>a[j])的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！