LINUX.ORG.RU

Си Среднее арифметическое больших чисел

 ,


1

1

Нужно найти среднее арифметическое большого количества относительно больших чисел. Пока задача своится к поиску среднего арифметического 30000 чисел, каждое из которых примерно равно 20000 (+-500). Данные поступают из файла.

Самое простое - писать в массив, потом сумму делить на количество. Сумму хранить, разумеется, в double. Но, так как файл может быть произвольной длины, теоретически могут загрузить и файл раз в 100 больше. Есть желание использовать какой-нибудь более продвинутый алгоритм, пусть даже более затратный с точки зрения процессора. Знаете какой-нибудь такой?


Сумму хранить, разумеется, в double

это почему?

Если числа большие, берёшь libgmp или bignum из openssl и считаешь

Harald ★★★★★ ()

Ну например читать в массив не нужно, можно делать это построчно, если числа записаны по одному в строке, и суммировать их, попутно подсчитывая их количество.

WRG ★★★★ ()

А что тебе мешает разбивать поток данных на подпотоки?
Например входные числа 2,3,4,5. Среднее 3.5.
Разбиваешь на 2 и 3 среднее 2.5
4 и 5 среднее 4.5
2.5 и 4.5 среднее 3.5

Это позволит тебе при очень небольшом объёме памяти считать среднее для ввода практически любого объёма.

Stahl ★★☆ ()

считайте порционально

int13h ★★★★★ ()

Вангую школьную задачу на замену кода (a+b)/2 на a + (a-b)/2

kim-roader ★★ ()

20000
больших чисел

man дроби

Продвинутый алгоритм из 3го класса:

(a + b + c)/3 = a/3 + b/3 + c/3 или (a + b)/3 + c/3

anonymous ()

Но, так как файл может быть произвольной длины, теоретически могут загрузить и файл раз в 100 больше. Есть желание использовать какой-нибудь более продвинутый алгоритм, пусть даже более затратный с точки зрения процессора

не очень понятно, зачем какой-то продвинутый алгоритм нужен тогда. для экономии памяти?

MyTrooName ★★★★★ ()

0. используеш уже вышеуказаную либу длинной целой арифмы

храниш два числа: текущую сумку и число чисел эту сумму сложивших.

ещё одна переменная на чтение очередного числа.

при потребности вызнать текущую арифметически среднюю любым разумным способом выдаёш точный ответ.

1. если в твоих ограничениях то int32(4 байтного целого достаточно).

1.1. / % штатные ( тока если суммка меньше нулика, следует акуратность проявить)

qulinxao ★★☆ ()

своится к поиску среднего арифметического 30000 чисел, каждое из которых примерно равно 20000 (+-500)

hint1: среднее арифметическое = сумма / количество :-)

hint2: сумма со свистом помещается в uint32 : avg(0..i,Const+f(i))=Const+avg(0..i,f(i))

соответсвенно встречный вопрос : вы хотите услышать тут быстрый метод сложения целых, чтения из файла или деления двух чисел? :-)

MKuznetsov ★★★★★ ()
Последнее исправление: MKuznetsov (всего исправлений: 1)
Ответ на: комментарий от MKuznetsov

А что мешает просто в столбик складывать, поразрядно?выделил память этак знаков на 30, вот тебе и 30-ти разрядное число...на том же list<int> можно реализовать операцию сложения, а деление через сложение выводится, хотя я конечно понимаю что это хардкор, однако проблем с переполнением точно не будет

energyclab ()
Ответ на: комментарий от energyclab

на том же list<int> можно реализовать

с тегом «Си» list<int> является офтопом :-)

А что мешает просто в столбик складывать, поразрядно?выделил память этак знаков на 30, вот тебе и 30-ти разрядное число...на том же list<int> можно реализовать операцию сложения, а деление через сложение выводится, хотя я конечно понимаю что это хардкор, однако проблем с переполнением точно не будет

жестокая жесть :-) реализуй если не лень, не забудь тут опубликовать это решение, чисто поржать :-)

MKuznetsov ★★★★★ ()
Ответ на: комментарий от energyclab

И сколько же времени он будет это считать? 10минут?

18446744073709551615 / ((20000 + (500/2)) = 910950324627632 чисел = 1821900649255264 байт = в среднем 1,6эксабайт.

18446744073709551615 / 4294967295(uint32_t max) = минимум 16гигабайт.

Т.е. никаких проблем с суммой 32битных интов в мире не существует, зачем нужно твоё предложение?

carb_blog10 ()
Ответ на: комментарий от carb_blog10

Видимо меня не так поняли или я не так понял проблему... Никаких эксабайт...Из школьного курса: Тип данных, который оперирует числами, например с разрядностью в 1000 знаком, ясно, что ни в один простой тип это не поместится... Поэтому и предложил сделать что то типа (раз си, так нате вам си):

{
...
char   res[1000] = {0};
int    count = 0;

while(fp != EOF) {// или другое нужное условие
    add_res(res, fp);
}

div_res(res, count);
...
}

void add_res(char *res, FILE *) {
  char   cur[1000] = {0};  
  int    buf;

  //читаем строку из потока в cur (в данном случае надо   реверсивно)
  ...

  for(int i = 0; cur[i] && i < 1000; ++i) {
    buf = (cur[i] - '0') + res[i];
    if(buf > 9) {
      shift(res, i, buf);
    }
    else {
      res[i] = buf;
    }
  }
}

void shift(char *res, int i, int buf) {
  res[i] = buf % 10;
  buf /= 10;
  for(int j = i + 1; res[j] && j < 1000; ++j) {
    if((res[j] + buf) > 9) {
      shift(res, j, res[j] + buf);
    }
    else {
      return;
    }
  }
}

Функцию div можно посмотреть как сделать, мне пока ничего кромне машинно зависмых механизмов не приходит в голову. (обратный код и т.д.), но на то есть wiki

energyclab ()
Ответ на: комментарий от energyclab

А время здесь при наилучших условиях - n*n , при хучших же n*(n + k) , к - кол-во разрядов для смещения

energyclab ()
Ответ на: комментарий от energyclab

Видимо меня не так поняли или я не так понял проблему...

Я понял суть твоего решения. Только вот это в тысячи раз медленней нормального.

Никаких эксабайт...

Суть не в том, что у тебя эксабайт, а суть в том, что у автора числа 16бит и в 64битный инт влезает сумма 1.6эксабайта этих чисел. Т.е. как ты понимаешь в реальных условиях 64битного инта хватит на сумму любого кол-ва реальных данных.

Тип данных, который оперирует числами, например с разрядностью в 1000 знаком, ясно, что ни в один простой тип это не поместится... Поэтому и предложил сделать что то типа (раз си, так нате вам си):

Суть в том, что никому не нужны такие числа - в них не считают.

Если даже автор будет считать сумму 32битных интов, то в 64битный инт влезет 16гигабайт 32битных интов. Как ты понимаешь 16гигабайт данных всяко больше нужных ему мегабайт. Да и реально считать сумму 16гигабайт почти никому не нужно.

А вот твой «на те вам си» будет считать эти 16+гигабайт тысячу лет. Зачем он нужен для данной задачи?

carb_blog10 ()
Ответ на: комментарий от energyclab

А время

Так «время» считаю в детсаде и к реальности оно не имеет никакого отношения и абсалютно бессмысленна.

Тут считается и учитывается только константа - цена операции. Во сколько раз она будет больше я уже сказал.

Есть реально настолько больные на головку, которые хранят числа в строках? Пичально.

carb_blog10 ()
Ответ на: комментарий от carb_blog10

Так «время» считаю в детсаде и к реальности оно не имеет никакого отношения и абсалютно бессмысленна.

Да! Да! Еще! Уииии!!11

anonymous ()

30000 чисел

20000+/-500

int returnAverage() {
        return 20000;
        // небольшие погрешности не учитываем
}
anonymous ()
Ответ на: комментарий от anonymous

мвахахаха

лучший ответ! в квотезы!

anonymous ()
Ответ на: комментарий от energyclab

А время здесь при наилучших условиях - n*n

Вот поэтому надо брать готовые библиотеки, типа GMP. Там на уровне O(n^(1.465)) вместо O(n^2).

i-rinat ★★★★★ ()
Ответ на: комментарий от anonymous

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

energyclab ()
Ответ на: комментарий от energyclab

че? я краба чмырю за высказывания вроде «О нотация - детсад»

anonymous ()

А почему нельзя сразу суммировать и считать количество, пока читаешь?

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

А если не влезу в double? Файл может быть любой длины. 100500 строк.

JANB ()
Ответ на: комментарий от Deleted

SOLVED

Два чаю этому господину!

По-моему, это единственное правильное решение.

JANB ()
Ответ на: комментарий от energyclab

Интересно, но сложновато и оверхеад. vmx предложил более простое решение. Но, в любом случае спасибо!

JANB ()
Ответ на: комментарий от Harald

Если числа большие, берёшь libgmp или bignum из openssl и считаешь

Вообще не был в курсе про эти либы. Спасибо!

JANB ()
Ответ на: комментарий от anonymous

Продвинутый алгоритм из 3го класса:
(a + b + c)/3 = a/3 + b/3 + c/3 или (a + b)/3 + c/3

Мы заранее не знаем количество чисел. Задача - не хранить большие объемы, а оперировать дельтами. Как и подсказал vmx

JANB ()
Ответ на: комментарий от i-rinat

Вот поэтому надо брать готовые библиотеки, типа GMP

для чисел, которые влезают в int32_t? Ты в своём репертуаре.

emulek ()
Ответ на: комментарий от Eddy_Em

А почему нельзя сразу суммировать и считать количество, пока читаешь?

так любой дурак сможет. А ты попробуй «на уровне O(n^(1.465))».

emulek ()
Ответ на: комментарий от JANB

А если не влезу в double?

ты до этого не доживёшь.

К тому же ты писал: «30000 чисел».

В любом случае, тебе грозит лишь потеря точности. Конечно она может быть очень большой, если рядом расположены разные числа. Типа 1+2+3+4+100500-100500+6. Если оно так, то числа надо ранжировать, например по степеням двойки(их немного IRL).

emulek ()
Ответ на: комментарий от emulek

Ты в своём репертуаре.

Ты тоже: «нить не читай @ сразу отвечай». Что сказать-то хотел?

i-rinat ★★★★★ ()
Ответ на: комментарий от JANB

Это физически невозможно.

Посчитай, какого размера должен быть твой файл, чтобы с int64 ты не влез в double!!!

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от i-rinat

Что сказать-то хотел?

то, что тут double и так хватит.

emulek ()
Ответ на: комментарий от emulek

Я цитировал часть сообщения, на которое отвечал. Ты читал цитату?

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

Я цитировал часть сообщения, на которое отвечал. Ты читал цитату?

читал. А ты читал первый пост? Или ты читал только ту фразу, на которую ответил?

emulek ()
Ответ на: комментарий от emulek

читал. А ты читал первый пост? Или ты читал только ту фразу, на которую ответил?

Ну и как это твоё сообщение отвечает на первый пост? Или для тебя правила другие, и тебе позволено отвечать на конкретное сообщение?

i-rinat ★★★★★ ()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от i-rinat

вроде не дурачок, а на клоуна время тратишь. иди лучше поней смотри

anonymous ()
Ответ на: комментарий от i-rinat

Ну когда ты наконец поймёшь, что без дурачка в деревне скучно? Хотя бы постарайся его не обижать непосильными его разуму вопросами. Пожалуйста!

anonymous ()
Ответ на: комментарий от i-rinat

В этом сообщении я тебе писал, и не пытался решить проблему ТСа. А вот ты пытался, fail.

emulek ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.