Оптимизация программной обработки структурированного ввода для больших данных - PullRequest
Новая
       14

Оптимизация программной обработки структурированного ввода для больших данных

0 голосов
/ 28 октября 2018

У меня есть одно задание.Чтобы сделать это более понятным, я буду использовать картинку ниже в качестве примера.Вход и выход разделены пунктирной линией.Первая строка ввода - это число N - количество комплектов.Для каждого набора в первой строке 2 числа - первая объявляет, сколько чисел я собираюсь обработать, а вторая - количество интервалов.Вторая строка указывает числа для обработки, а третья строка содержит 2 числа X и Y , которые создают и интервал.Для каждого интервала я должен вывести 3 числа - наименьшее число на интервале, индекс наибольшего числа на интервале и XOR всех чисел.Все работает хорошо, за исключением того, что это действительно медленно для больших данных, и я не знаю, как заставить работать быстрее.Я приложил свой код и большой ввод данных.

input.txt 

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int id;
  int index;
} Censor;


int Xor(const int x, const int y, const Censor array[]) {
  int xor = array[x].id;
  if (x == y) {
    return xor;
  }
  for (int i = x + 1; i <= y; i++) {
    xor ^= array[i].id;
  }
  return xor;
}

int int_cmp(const void *a, const void *b) { 
    const Censor *ia = (const Censor *)a; 
    const Censor *ib = (const Censor *)b;
    return (ia->id  - ib->id); 
} 

int LowestId(const int x, const int y, Censor array[]) {
  int id = array[x].id;
  if (x == y) {
    return id;
  }
  qsort(array, y - x + 1, sizeof(Censor), int_cmp);
  return array[0].id;
}

int HighestIdIndex(const int x, const int y, Censor array[]) {
  int index = array[x].index;
  if (x == y) {
    return index;
  }
  qsort(array, y - x + 1, sizeof(Censor), int_cmp);
  return array[y].index;
}

int main() {
  int t, n, q, b, e;
  int max = 100;
  int count = 0;
  int *output = (int *)malloc(max * sizeof(output));
  scanf("%d", &t); //number of sets
  for (int i = 0; i < t; i++) {
    scanf("%d %d", &n, &q);
    //I am making 3 separate arrays for numbers, because some of them are being sorted and some of them not
    Censor lowest_id[n];
    Censor highest_id_index[n];
    Censor xor[n];
    //This loop fills arrays with the numbers to be processed
    for (int j = 0; j < n; j++) {
      scanf("%d", &(lowest_id[j].id));
      lowest_id[j].index = j;
      highest_id_index[j].id = lowest_id[j].id;
      highest_id_index[j].index = j;
      xor[j].id = lowest_id[j].id;
      xor[j].index = j;
    }
    // Now I am scanning intervals and creating output. Output is being stored in one dynamically allocated array.
    for (int k = 0; k < q; k++) {
      scanf("%d %d", &b, &e);
      if (count + 3 >= max) {
        max *=2;
        int *tmp = (int *)realloc(output, max * sizeof(tmp));
        if (tmp == NULL) {
          return 1;
        } else {
          output = tmp;
        }
      }
      output[count++] = LowestId(b, e, lowest_id);
      output[count++] = HighestIdIndex(b, e, highest_id_index);  
      output[count++] = Xor(b, e, xor);
    }
  }
  printf("---------------------\n");
  for (int i = 0; i < count; i++) {
    printf("%d\n", output[i]);
  }
  free(output);
  return 0;
}

1 Ответ

0 голосов
/ 28 октября 2018

Спасибо @Dan Mašek и @Alex Lop.Сортировка подмассива в этом случае была ненужной.Гораздо проще перебрать подмассив с линейной сложностью.

...