Действительно ли умножение является инверсией лучше или хуже?

Ваша adjacencyList конструкция неверна.

Заменить adjacencyList[i[0]].append(i[0]) на adjacencyList[i[0]].append(i[1]). Я не вижу никаких петель внутри другого. Ваша сложность времени составляет O(n).

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

После изменения ваш вывод должен быть

[[1, 2], [0, 3], [0, 4, 5], [1], [2, 6], [2], [4]]

Отсюда вы можете интерпретировать, что 0 имеет 1 и 2 в качестве соседей. 2 имеет 0 и 3 соседей, 3 имеет 0,4 и 5 в качестве соседей и т. Д.

Обратите внимание, что этот подход не работает, если у вас есть такие узлы, как {2, 60, 1000, 4}. В этом случае лучше использовать словарь узлов и список соседей.

11
задан 9 revs, 5 users 81%anon 23 May 2017 в 12:07
поделиться

11 ответов

Умножение на инверсию быстрее. Компиляторы не оптимизируют это автоматически, потому что это может привести к маленькой потере точности. (Это на самом деле подошло на группе новостей D, которую часто посещает Walter Bright, и он прояснил, что компиляторы не делают этого автоматически.) Необходимо обычно делиться, потому что это более читаемо и точно.

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

18
ответ дан 3 December 2019 в 00:54
поделиться

То, какой "быстрее", является действительно конкретным вопросом CPU, или по крайней мере сколько быстрее конкретный ЦП, да, подразделение обычно замечается как медленнее, чем умножение. И конечно на все вопросы производительности можно ответить с "им, зависит".

ОДНАКО, если Вы спросили, который "лучше", а не который быстрее был бы четкий ответ, более читаемый лучше. Повышение производительности, на которое Вы смотрите, вероятно на порядке нескольких тактов, поэтому если Вы не говорите о выполнении этого миллионы времен, Вы пытаетесь сохранить себя микросекунды. И нет никакой оптимизации микросекунды, которая стоит пожертвовать удобочитаемостью и пригодностью для обслуживания.

11
ответ дан 3 December 2019 в 00:54
поделиться

Преимущество будет очень небольшим или обнулит и, в зависимости от компилятора и, в зависимости от аппаратных средств.

Но это могло все еще иметь значение (в жестком цикле), и затем для удобочитаемости необходимо записать

SquareInches = MMSquared * (1 / 645.16)

И предпочтительно используйте константу для 645,16.

11
ответ дан 3 December 2019 в 00:54
поделиться

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

Таким образом, если это не на самом деле проблема производительности, я, вероятно, не волновался бы об этом. Выберите коэффициент преобразования, это более понятно.

5
ответ дан 3 December 2019 в 00:54
поделиться

от моего VB кодируют таймер

Dim SquareInches As Double
Dim MMSquared As Double = 81
Const d As Double = 645.16
Const m As Double = 1 / 645.16
Private Function TestCase1() As Boolean 'One
    'Test One Code Here
    SquareInches = MMSquared / d
    'end test code
    Return True
End Function
Private Function TestCase2() As Boolean 'Two
    'Test Two Code Here
    SquareInches = MMSquared * m
    'end test code
    Return True
End Function

результаты

     3/17/2009 2:13:27 PM   CPU - 1.794GHz
 One - Using Division
 Two - Using Multiplication
 Outer Loops(OL)=7  Inner Loops=262,144
  ( times in ticks.  1 ms. = 10,000 ticks )
 >> Two faster, 0.0488 ticks/loop
  Ticks / Loop
 0.0342         0.0819          0.0331          0.0488
 OL Base        One             Two              One - Two
 1   8,936          21,459          8,609           12,850
 2   9,008          21,416          8,682           12,734
 3   8,965          21,423          8,643           12,780
 4   8,964          21,457          8,659           12,798
 5   8,966          21,469          8,640           12,829
 6   8,987          21,660          8,688           12,972
 7   8,963          21,429          8,802           12,627

  Average
 8,969          21,473          8,674           12,799
  Variance
 431.4          6,160.3         3,315.9       
  Standard Deviation
 20.8           78.5            57.6          
 3/17/2009 2:13:27 PM
4
ответ дан 3 December 2019 в 00:54
поделиться

Алгоритмы подразделения медленнее, чем алгоритмы умножения в большинстве случаев.

Это - компромисс, можно выбрать или более читаемый путь или более быстрый путь.

// Using division operation
SquareInches = MMSquared / 645.16 

Это легко считать и поддержать, но работает медленнее, чем его мультипликативный дубликат:

// Using a multiplication 
SquareInches = MMSquared * 0.0015500031000062000124000248000496

Если Вы пойдете этим путем, то Вам будет нужно больше пространства в памяти для хранения обратных цифр числа, но выполнений алгоритма substancially быстрее. Пользователь протестировал его на проекте VS2005 и сообщил 8X более быстрая производительность для мультипликативной версии.

Причина этого состоит в том, что умножение может быть вслепую преобразовано, чтобы сместить и добавить операции на процессоре, которые являются наиболее оптимизированными операциями на ЦП. Хороший алгоритм для умножения со знаком является алгоритмом Booth (процессор делает это для Вас). С другой стороны, больше управления наверху требуется при выполнении алгоритма подразделения, таким образом рендеринге алгоритмов подразделения медленнее.

Если производительность является Вашей потребностью, используйте дополнения, вычитания (не что иное как добавление дополнения two), умножение, смещения, но никогда подразделения. Вы получили бы существенное ненезначительное улучшение, если Вы вычисляете все свои инверсии заранее и используете их для умножения в подразделении интенсивной программы.

3
ответ дан 3 December 2019 в 00:54
поделиться

Относительно компиляторов, выполняющих оптимизацию к mult, они могут оптимизировать это (GCC делает): SquareInches = MMSquared * (1 / 645.16).

1
ответ дан 3 December 2019 в 00:54
поделиться

Если Вы делитесь на литеральное значение как 645.16 затем вероятно, что нет никакого различия, потому что компилятор может легко определить, какая версия быстрее, и используйте это.
Если Вы делитесь или умножаетесь переменной затем, вероятно, что умножение немного быстрее, потому что логика обычно более проста.
Как с чем-либо, что и говорить, используют профилировщика.

0
ответ дан 3 December 2019 в 00:54
поделиться

Умножается и добавляет, самые быстрые операции поддержки процессора. Некоторые процессоры даже не имеют аппаратных реализаций вещей как подразделение, квадратный корень, и т.д.

0
ответ дан 3 December 2019 в 00:54
поделиться

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

Если это будет интерпретируемый язык, то количество времени, чтобы считать источник и преобразовать его в числа сокрушит время, потраченное, чтобы на самом деле сделать математику, особенно при использовании этого много значащих цифр для умножения. (Вы уверены, что Вам действительно нужно это много значащих цифр?)

0
ответ дан 3 December 2019 в 00:54
поделиться

Я думал бы, что первый метод ясно предпочтен, потому что это явно. Предположите находить это в чужом коде. Как Вы уверены, что 0.00155... действительно 1/645.16? Что, если исходный программист сделал ошибку? Кроме того, как я знаю, что 645.16 корректный коэффициент преобразования? Всегда лучше не оставить числа уплотненными или представленными в универсальной форме для простоты. Самый основной пример следующие:

//hours per day * days per year
int hoursPerYear = 24*365;

Мы можем ясно видеть, что это число корректно, но как Вы знали бы, бесцеремонно, что 8760 корректный ответ? Если необходимо выполнить многие из этих операций, можно хотеть предварительно обработать данные к правильной форме ПРЕЖДЕ, ЧЕМ ввести интенсивные вычисления. Этим способом Вам не будет нужна невероятная эффективность, и вопрос становится спорным.

0
ответ дан 3 December 2019 в 00:54
поделиться
Другие вопросы по тегам:

Похожие вопросы: