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

это почему?

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

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

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

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

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

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

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

man дроби

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

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

https://gmplib.org/

На эрланге твоя задача решается в лоб.

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

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

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

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

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

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

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

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

да, царя каставали?

Знаете какой-нибудь такой?

Iterative mean?

http://www.heikohoffmann.de/htmlthesis/node134.html

double
mean_iter(int *arr, size_t n)
{
        double avg = 0;
        int i;

        for (i=0; i<n; i++) {
                avg += (arr[i] - avg) / (i + 1);
        }

        return avg;
}

Да.

Здесь нужен MapReduce!

MapReduce Explained

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

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

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

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

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

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

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

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

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

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

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

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

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

Видимо меня не так поняли или я не так понял проблему... Никаких эксабайт...Из школьного курса: Тип данных, который оперирует числами, например с разрядностью в 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

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

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

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

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

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

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

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

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

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

А время

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

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

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

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

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

30000 чисел

20000+/-500

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

мвахахаха

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

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

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

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

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

Сори, не тебе коммент дал случайно

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

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

SOLVED

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

http://bash.im/quote/394985

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