Виртуальная конкатенация с массивами

Question

Предположим, у меня есть 3 массива двойной точности a1[], a2[], a3[] каждый длиной L1, L2, L3

Предположим, я хочу объединить эти массивы "виртуально". То есть я хочу создать виртуальный массив a_virtual[] такой, что a_virtual = {a1[L1], a2[L2], a3[L3]} логически, хотя физически эти массивы не могут быть смежными друг с другом.

Так что, если я хочу получить доступ к a_virtual[5] и L1=2, L2=3, L3=1, тогда будет a3[0]. Для доступа к a_virtual[0], a1[0] будет извлечено

Как бы я это сделал

• в С
• в C ++ (как это сделать с помощью std :: vectors вместо массивов также будет полезно)
• в CUDA

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

Answer 1

Вот возможное решение в C, использующее связанный список и (хвостовую) рекурсию:

#include <stdio.h>

struct dblarr {
    double *data;
    size_t len;
    struct dblarr *next;
};

double *fetch(const struct dblarr *arr, size_t index) {
    if (arr == NULL) return NULL;
    if (index < arr->len) return arr->data + index;
    return fetch(arr->next, index - arr->len);
}

int main(void) {
    double a1[2] = {1, 2};
    double a2[3] = {1, 2, 3};
    double a3[1] = {1};
    struct dblarr x1, x2, x3;

    x1.data = a1; x1.len = sizeof a1 / sizeof *a1; x1.next = &x2;
    x2.data = a2; x2.len = sizeof a2 / sizeof *a2; x2.next = &x3;
    x3.data = a3; x3.len = sizeof a3 / sizeof *a3; x3.next = NULL;

    printf("before %f\n", *fetch(&x1, 5));
    *fetch(&x1, 5) = 0.42;
    printf(" after %f\n", *fetch(&x1, 5));

    return 0;
}

Вы можете «увидеть работающий код» на http://ideone.com/mY0ix.

Answer 2

Некоторые другие дают ответ для базовой реализации языка Си.

Ниже приведен пример кода для реализации класса C ++ общего назначения, которая создает виртуальные каскадные массивы без копирования каких-либо элементов массива. После создания виртуальный массив может быть проиндексирован как обычный вектор (для чтения или записи):

#include <vector>
#include <map>
#include <iostream>;
using namespace std;

class VirtualArray {
public:
    multimap<int,double*> startIndices;  // reverse map of starting index to its sub array
    int size;

    VirtualArray() : size(0) {}

    double & operator[](int i) {
        // find proper subarray in log(n) time
        multimap<int,double*>::iterator iter = --startIndices.upper_bound(i);
        double *subarray = iter->second;
        int startIndex = iter->first;

        // index into subarray
        return subarray[i-startIndex];
    }

    void addArray(double* array, int length) {
        startIndices.insert(make_pair(size, array));
        size += length;
    }

    void addVector(vector<double> & vec) {
        startIndices.insert(make_pair(size, vec.data()));
        size += vec.size();
    }
};

int main() {
    double a1[3], a2[4], a3[6] = {1, 2, 3, 4, 5, 6};
    int L1 = 3, L2 = 4, L3 = 6;

    vector<double> a3vec;
    a3vec.assign(a3,a3+6);

    VirtualArray vArray;
    vArray.addArray(a1,L1);
    vArray.addArray(a2,L2);
    vArray.addVector(a3vec);

    cout << vArray[10];
    return 0;
}

Answer 3

Как насчет чего-то вроде следующего? Это довольно жестко закодированный и не самый лучший / чистый код, но, может быть, вы можете обобщить эту логику?

#include <iostream>
#include <vector>
using namespace std;

void logicalConcat(vector<int>& a1, vector<int>& a2, vector<int>& a3, int k) {

    if(k > a1.size() - 1)
        k -= a1.size();
    else { 
        cout << a1[k] << endl;
        return;
    }

    if(k > a2.size() - 1)
        k -= a1.size();
    else {
        cout << a2[k] << endl;
        return;
    } 

    cout << a3[k] << endl;
}

Здесь k будет индексом виртуальной конкатенации, которую вы хотите. Мы ничего не объединяем, просто перебираем векторы.

Answer 4

Если массивы не обязательно должны быть смежными, то один из способов сделать это - преобразовать один индекс в два индекса, один для массива указателей на реальные массивы, а другой для массива, который имеет нужный элемент. 1001 *

Для этого вы должны создать массив указателей на эти массивы:

double** arrays = {a1, a2, a3};

затем массив их длин:

int arraysizes = { sizeof(a1) / sizeof(*a1), sizeof(a2) / sizeof(*a2), sizeof(a3) / sizeof(*a3) };

Затем, учитывая индекс n, вы можете вычислить два индекса для arrays, выполнив

int i1 = 0, j = 0;

while (n - arraysizes[j] >= 0)
    n -= arraysizes[j++], ++i1;

И вы можете затем индексировать массив указателей, чтобы получить фактический элемент:

arrays[n][i2]

Вы также можете создать класс-обертку для выполнения этой арифметики со встроенным operator[].