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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 13.12.2010, 16:29
Новичок

Отправить личное сообщение для Named Посмотреть профиль Найти все сообщения от Named
 
Регистрация: 13.12.2010
Сообщений: 2

Умножение :)
Задача такая:
есть два массива, A и B. Mассивы не упорядочены, массив А значительно меньше массива В.
Надо найти сумму произведений их элементов.

К примеру, заданы
A[1] = 2; A[9] = 1; A[64] = -2;
B[1] = 2; B[2] = 1; B[3] = 2; B[4] = -1; B[5] = 0; B[64] = 1;
Соответственно, сумма будет 2*2 + 1*0 + -2*1 = 4+0-2 = 2.

Пишу на PHP, реализация пока наиболее быстрая такова:
Код:
	$result = 0;
	foreach ($array1 as $key=>&$value)
		$result += $value*$array2[$key];
	return $result;
Есть ли возможность как-либо ускорить?
  #2  
Старый 13.12.2010, 17:51
Новичок

Отправить личное сообщение для Akina Посмотреть профиль Найти все сообщения от Akina
 
Регистрация: 26.11.2010
Сообщений: 5

По-моему, очевидно, что потребуется count(A) умножений и столько же сложений. И поисков по массиву B. Так что ускорение можно получить разве что от снижения накладнЫх расходов на доп. операции. А у тебя их и так, похоже, минимум...
  #3  
Старый 16.12.2010, 22:10
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

Цитата:
массив А значительно меньше массива В.
A[64], B[64]
А по-моему они равны
Цитата:
Надо найти сумму произведений их элементов.
\sum_{i=1}^n{({x_{i}}*{y_{i}})}

Код:
SIZE = min(sizeof(A)/sizeof(A[0]),  sizeof(B)/sizeof(B[0]); 
SUM = 0;

for ( i = 0; i < SIZE; i++) {
    if (  A[i] != 0 || B[i] != 0 ) // а толку :)
      SUM += A[i]*B[i];
}
Цитата:
Есть ли возможность как-либо ускорить?
Да - выкинуть PHP.

Последний раз редактировалось pavlinux, 16.12.2010 в 22:27.
  #4  
Старый 18.12.2010, 12:31
Новичок

Отправить личное сообщение для Named Посмотреть профиль Найти все сообщения от Named
 
Регистрация: 13.12.2010
Сообщений: 2

Сообщение от pavlinux Посмотреть сообщение
А по-моему они равны
Да нет, в одном максимум 20 элементов может быть, а в другом несколько сотен или тысяч.
Я сейчас говорю не о занимаемом в памяти месте, а о числе перебираемых элементов в цикле foreach.
В том коде, что вы привели, вместо 3 операций будет происходить 64, что явно не хорошо.
  #5  
Старый 05.01.2011, 00:16
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

Сообщение от Named Посмотреть сообщение
вместо 3 операций будет происходить 64, что явно не хорошо.
Имеем, скажем 5 элементов, случайного массива: A[ ]= a, A[ ]= b, A[ ]= x, A[ ]= y, A[ ]= z;
A[] - пусто, так как мы не знаем значения индексов.
Только знаем, что 5 из 64 не пустые.

Чему равно p+q+x+y+z

Вот так в реальности звучит ваша задача.

Последний раз редактировалось pavlinux, 05.01.2011 в 00:38.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Умножение по модулю, актуально в течение 20 часов гость Математические алгоритмы (другое) 2 16.10.2009 03:32
графическое умножение persicum Математические алгоритмы 4 28.01.2007 22:43
графическое умножение persicum Математические алгоритмы 0 14.01.2007 18:23
быстрое умножение на дельфи persicum Реализация, исходники, языки 0 11.01.2007 14:26