Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > выборка чисел

Автор: oleg1973 6.2.2004, 21:35

кароче есть массивчик на примерно 500.000 елементов
нада создать другой в котором будут все элементы встречаюсиеся в первом (тоесть без повторений)
написал я но работает секунд 40 на р4 2000
делаю так
к примеру начальный массив А конечный В, С счетчик елементов в массиве В
беру елемент из А сравниваю с В стока раз скока С (чтоб весь массив не пробегать )
ну и так далее

поражает медленность работы

идеи есть?

Автор: December 6.2.2004, 23:08

oleg1973 Давай чуть подробнее, по-русски.

Автор: bagira 6.2.2004, 23:24

А элементы какого типа - числа или строки?

Автор: acp 6.2.2004, 23:31

Цитата

А элементы какого типа - числа или строки?

А разница?

2 oleg1973
Исключающая сортировка

Автор: bagira 7.2.2004, 00:04

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

А в принципе, для сортировки не важно, какой тип...

Автор: Дрон 7.2.2004, 13:08

Вот придумал небольшой алгоритм, который работает гораздо быстрее описанного тобой.
Будут вопросы -- спрашивай.
Написан на Борланд C++

Код

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

// Функция fill
// src -- указатель на исходный массив
// dst -- указатель на массив для результата
// len -- длина исходного массива
// возвращеет кол-во различных чисел
int fill(int *src,int *dst, int len){
 if(len==0) return 0; // если длина 0
 int v=dst[0]=src[0]; // присваиваем первому эл-ту dst значение первого эл-та src
 if(len==1) return 1;

 int *work = new int[len]; // рабочий массив

 int len1=0;
 int len2=0;
 for(int i=1;i<len;i++){
  if(src[i]>v){
   work[len1]=src[i]; // в рабочий массив -- все эл-ты большие v
   len1++;
  } else if (src[i]<v){
   len2++;
   work[len-len2]=src[i]; // в конец -- все эл-ты, меньшие v
  }
 }

 int res = 1;
 res += fill(work,dst+res,len1); // рекурсивный вызов для первого куска (начало work)
 res += fill(work+len-len2,dst+res,len2); // для второго куска

 delete work;
 return res;
}


// А вот это, как я понимаю было у тебя
// Можешь сравнить быстродействие для большого разброса чисел
int fill_old(int *src,int *dst,int len){
 int c=0;
 int i,j;
 for(i=0;i<len;i++){
  for(j=0;j<c;j++){
   if(src[i]==dst[j]) { break; }
  }
  if(j==c) { dst[c]=src[i]; c++; }
 }
 return c;
}


#define SIZE 500000

// А это main :), чтоб посмотреть как работает
void main(){
 randomize();
 int *src = new int[SIZE];
 int *dst = new int[SIZE];

 for(int i=0;i<SIZE;i++){
  src[i]=random(100);
  dst[i]=0;
 }

 int count = fill(src,dst,SIZE);

 printf("%i\n",count);

 for(int i=0;i<count;i++){
  printf("%2i  ",dst[i]);
 }

 getch();
}

Автор: Дрон 7.2.2004, 13:22

Одно важное замечание к работе данного алгоритма:
Исходный массив должен содержать случайную последовательность чисел, если же она отсортирована (или близка к этому), тогда всё -- дас ист капут

Сожрёт полгига памяти и будет очень долго думать.

Так уж он устроен.

Автор: Дрон 7.2.2004, 13:50

Это опять я. Немножко подумал и вот о чём

С прошлым моим замечанием можно хорошо бороться, если оптимизировать выбор начального элемента, т.е. значение числа v.
Например вот так:

заменить строку

Код

int v=dst[0]=src[0];

на

Код

int v=dst[0]=src[len/2];

и ещё заменить

Код

for(int i=1;i<len;i++){

на

Код

for(int i=0;i<len;i++){

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

Автор: oleg1973 7.2.2004, 13:56

December
ну я имел ввиду из массива выбрать уникальные числа
тоесть если к примеру в массиве А число 2 встречается 100 раз
то в массив В мы засунем всего одну 2 а не 100

ну не знаю я как точнее обяснить

Автор: Sardar 7.2.2004, 16:37

Что ты точно знаешь об этом массиве(остортирован, где то предсказуем...)?

Основная работа это поиск уже добавленных элементов. Сильно ускорить поиск можно используя хеширование, т.е. тебе надо написать HashSet(хешированное множество). В зависимости от размера ковши также могут быть хешированны.

Дугой способ - отсортированые многослойные связанные списки. Это реализовать чуть сложнее. Многослойные это значит, что ты имеешь не только ссылки на обеих соседей, но и на другие(каждый пятый, одинадцатый...) элементы. Благодаря многослойности можно быстро передвигатся по списку. Так как это связанный список, тебе дешево вставлять в любое место новые элементы, т.е. держать список отсортированным. Так как список отсортирован ты можешь использовать бинарный поиск. Ну а дальше ищем, если нет элемента, то вставляем его в список.

Для большей инфы иди на http://algolist.manual.ru.

Автор: oleg1973 7.2.2004, 17:35

Sardar
массив не отсортирован и абсолютно рандомный

Автор: Дрон 7.2.2004, 18:00

Э-э...
А что моя идея не подходит?

Автор: Sardar 7.2.2004, 19:33

Цитата

массив не отсортирован и абсолютно рандомный

Ну тогда хеш-множество или сортированные многослойные связанные списки. Что это я написал выше.

Цитата

А что моя идея не подходит?

Дрон по моему ты привел код быстрой сортировки...

Автор: Дрон 7.2.2004, 19:40

Цитата

Дрон по моему ты привел код быстрой сортировки...

И да, и нет.

Я использовал идею похожую на быструю сортировку. Но только похожую.

Вы бы посмотрели результат работы.
Она выдаёт "почти отсортированный" по убыванию массив.
Но это не сортировка, а именно решение задачи, поставленной oleg1973.
Проверьте.

Я не говорю, что это оптимальное решение. Но ведь оно работает.
Причём очень быстро. Эти 500000 элементов обрабатываются за доли секунды. Что ещё надо?

Автор: remax 8.2.2004, 18:54

2 aсp

Цитата

А разница?

Разница есть. В зависимости от типа данных некоторые алгоритмы могут быть либо суперэффективными либо абсолютно неприемлемы.

Например, если данные имеют целочисленный тип и количество возможных комбинаций значений существенно меньше, чем оговоренные в условии 500000, то можно применить следующий алгоритм.

Цитата

// ar0 - исходный массив
// ar1 - временный массив, его размерность равна числу возможных значений.
Например, если тип элементов ar0 - word, to ar1[0..65535]
// ar2 - результирующий массив. Имеет смысл сделать динамическим

Этап1. Зануляем все элементы ar1
Этап2. Последовательно перебираем ar0 и увеличиваем на единицу соответствующий элемент ar1.
т.е. Inc(ar1[ar0[n]])
Этап3. Последовательно перебираем ar1. Номера всех ненулевых значений заносим в ar2

Достоинства метода:
1.нет вложенных циклов и рекурсий
2.не важно в каком порядке встречаются данные.
3.в результате мы знаем не только какие значения элементов были в исходном массиве но и сколько раз
4.результирующий массив отсортирован (либо по возрастанию либо по убыванию)

Ограничения.
1.Очень эффективен, если исходный массив имеет тип byte. Имеет смысл, если исходный массив имеет тип ShortInt или Word. Не приколен, если исходный тип Longint. Недопустим для вещественных типов данных.
2.тип элементов массива ar1 выбирается так, чтобы в одном элементе поместилось общее число элементов исходного массива ar0.

Автор: remax 8.2.2004, 19:17

В принципе, алгоритм можно переделать таким образом, что ar1 - array of boolean. Тогда на втором этапе надо делать не Inc, а присвоение True.

При этом - метод теряет достоинство №3 (см. предыдущий топик) но уходит ограничение 2. Кроме того, более мягкие требования к занимаемой памяти масивом ar1.

P.S. Эту идую можно развить и дальше - использовать одно битные значения, тогда каждый элемент массива ar1 будет содержать 8 флагов наличия соответствующих значений. Но в этом случае в 2-3 раза уменьшиться общее быстродействие метода.

Автор: December 8.2.2004, 23:59

Цитата(oleg1973 @ 7.2.2004, 13:56)

Чё надо сделать - я понял, ты перечитай как ты объясняешь свой метод - это даже не по-русски

Автор: Guest 9.2.2004, 00:15

Цитата

Сортировала по возрастанию (не важно как)

тут действительно так и просится устроить сортировку
только нужно выбрать сортировку время работы которой росло бы со скоростью меньше n*n (иначе можно простым перебором)

Цитата

Одно важное замечание к работе данного алгоритма:
Исходный массив должен содержать случайную последовательность чисел, если же она отсортирована (или близка к этому), тогда всё -- дас ист капут
Сожрёт полгига памяти и будет очень долго думать.
Так уж он устроен.

Цитата

С прошлым моим замечанием можно хорошо бороться, если оптимизировать выбор начального элемента, т.е. значение числа v

за критерий разделения массива на две части можно выбрать не значение элемента, а его индекс: делим массив на две половинки (первые 25000 и вторые 25000), сортируем их отдельно, а потом объединяем их
если не ошибаюсь, это называется "метод слияния"
время его работы и количество необходимой памяти зависит только от длины входного массива

вот, как это может выглядеть на C++:

Код

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

#define SIZE 65536

//получает два отсортированных массива размером size в результате выдает отсортированный массив длины 2*size
void Sort(int *source1,int *source2,int *result,int size)
{
  int c1,c2,c;
  int *buffer=new int[2*size];

  c1=0;
  c2=0;
  c=0;
  while(true)
  {
    if(c1<size)
    {
      if(c2<size)//оба массива еще не закончились, сравниваем их элементы
      {
        if(source1[c1]<source2[c2])
          result[c++]=source1[c1++];
        else
          result[c++]=source2[c2++];
      }
      else//второй массив закончился, первый - нет, дописываем его (первый) в result
        result[c++]=source1[c1++];
    }
    else
    {
      if(c2<size)//первый массив закончился, второй - нет, дописываем его (второй) в result
        result[c++]=source2[c2++];
      else//у нас все закончилось, уходим...
        break;
    };
  };
};
void main()
{
  int array1[SIZE];
  int array2[SIZE];//два массива, между ними будем гонять информацию, пока она не станет отсортированной
  int *source,*result,*bak;
  int c;
  int size;

  source=array1;
  result=array2;
  srand( (unsigned)time( NULL ) );
  for(c=0;c<SIZE;c++)
  {
    source[c]=rand();
    //printf("%d\n",source[c]);
  };
  printf("------------\n");
  size=1;//показывает размер маленьких массивов, на которые делим большой
  while(size<SIZE)
  {
    for(c=0;c<SIZE;c+=2*size)
      Sort(source+c,source+c+size,result+c,size);//слияние двух маленьких массивов
    size*=2;
    bak=result;//меняем местами источник и приемник
    result=source;
    source=bak;
  };
  printf("%d\n",source[0]);
  for(c=1;c<SIZE;c++)
  {
    if(source[c]!=source[c-1])//чтобы пропустить одинаковые элементы
      printf("%d\n",source[c]);
  };
};

тестировал я его на SIZE 16, вроде бы правильно работает
в таком виде он работает только, если SIZE - степень 2, его, конечно, можно как-нибудь приспособить к другим SIZE, но это уже не очень интересная задача, можно просто дополнять массив до нужного количества одним из его элементов: на результат это не повлияет, а время сильно не изменится...

Автор: maxim1000 9.2.2004, 00:17

это был я...