Многие люди прошивают leetcode.Сегодня я тоже подписался на игрушечную игру и обнаружил, что многие из них являются алгоритмическими вопросами.Ну, после 10 лет выпуска все плохие математические знания, которые я выучил, были возвращены в школа. Ладно, давайте без сплетен, давайте перейдем к делу, давайте посмотрим на первый вопрос, который я попробовал в нем сегодня, это немного интересно, это не просто простой алгоритм, но и данные и подходит ли он.
Предприятие
Нажмите на банк вопросов, прочитайте первый вопрос, давайте посмотрим на этот вопрос:
Учитывая массив целых чисел и целевое значение, найдите в массиве два числа, сумма которых равна целевому значению.
Вы можете предположить, что каждый ввод соответствует только одному ответу и что одни и те же элементы нельзя использовать повторно.
Пример:
Учитывая числа = [2, 7, 11, 15], цель = 9
потому что nums[0] + nums[1] = 2 + 7 = 9
Итак, верните [0, 1]
После использования стольких текстовых описаний, на самом деле это сводится к следующему: два числа в массиве нужно сложить, равное целевому значению, и найти индекс этих двух чисел.
Вопрос не сложный, литкод дает два алгоритма:
- Метод грубой силы итеративно определяет временную сложность O (n ^ 2), а пространственную сложность O (1).
- После хеш-таблицы сложность времени и пространства равна O (n)
закон о насилии
Я реализовал метод перебора на языке Go (golang), давайте посмотрим на код ниже.
func TwoSum1(nums []int, target int) []int {
n:=len(nums)
for i,v:=range nums {
for j:=i+1;j<n;j++ {
if v+nums[j] == target {
return []int{i,j}
}
}
}
return nil
}
Два слоя петель вложены друг в друга, очень желтые и буйные. Этот алгоритм заключается в том, что если вам повезет, результат будет получен путем повторения цикла дважды, если вам не повезло, искомый элемент находится ровно в двух последних цифрах, то это действительно O(n^2).
перемешивание
В языке Go есть тип карты, это реализация Hash по умолчанию, на основе этого мы используем Golang для реализации хеширования.
func TwoSum2(nums []int, target int) []int {
m:=make(map[int]int,len(nums))
for i,v:=range nums {
sub:=target-v
if j,ok:=m[sub];ok{
return []int{j,i}
}else{
m[v]=i
}
}
return nil
}
Этот алгоритм вполне удовлетворителен, а временная и пространственная сложность — O(n).Если повезет, в массиве будет много повторяющихся элементов, и занимаемое место будет меньше.
тестовое задание
После того, как алгоритм написан, его необходимо протестировать, чтобы убедиться, что результат правильный, а улун не допускается.
package main
import (
"flysnow.org/hello/lib"
"fmt"
)
func main(){
r1:=lib.TwoSum1([]int{2, 7, 11, 15},9)
fmt.Println(r1)
r2:=lib.TwoSum2([]int{2, 7, 11, 15},9)
fmt.Println(r2)
}
Рабочий вывод:
[0 1]
[0 1]
Как и ожидалось, с нашим алгоритмом проблем нет.
ожидания производительности
Эти два алгоритма также усложняли пространство и время. Из нашего собственного кода это также второй метод Hash, который намного лучше, чем насилие. Так ли это на самом деле? Мы используем Go Benchmark, проверено.
О бенчмарке (Benchmark) можно обратиться кБоевые заметки по языку Go (двадцать два) | Тест Go, здесь подробно описываться не будет.
func BenchmarkTwoSum1(b *testing.B) {
b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum1([]int{2, 7, 11, 15},9)
}
}
func BenchmarkTwoSum2(b *testing.B) {
b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum2([]int{2, 7, 11, 15},9)
}
}
бегать➜ lib go test -bench=. -benchmem -run=noneкоманда для просмотра результатов теста Golang Benchmark.
pkg: flysnow.org/hello/lib
BenchmarkTwoSum1-8 50000000 26.9 ns/op 16 B/op 1 allocs/op
BenchmarkTwoSum2-8 20000000 73.9 ns/op 16 B/op 1 allocs/op
Тестовый пример, который я использовал, прямо указан в вопросе.Мы обнаружили, что в случае этого тестового примера мы не оптимистичны в отношении метода грубой силы, но производительность в 2,5 раза выше, чем у метода хеширования, который кажется немного отличаться от того, что мы думали.
регулировка положения массива
Посмотрим на тестовый массив.Ответ находится в первых двух цифрах массива.Это действительно выгодно для метода грубой силы.Подгоняем два ответа 2 и 7 в конец массива,то есть тестовый массив является{11, 15, 2, 7}, посмотрите на результаты теста.
BenchmarkTwoSum1-8 50000000 29.1 ns/op 16 B/op 1 allocs/op
BenchmarkTwoSum2-8 10000000 140 ns/op 16 B/op 1 allocs/op
Ну, эта мелодия, метод грубой силы по-прежнему силен как никогда, но производительность метода хеширования упала в 1 раз, а метод хеширования был доработан до смерти.
Расширить количество массивов
Мы обнаружили, что при небольшом количестве массивов преобладает метод полного перебора и производительность является лучшей. Далее настраиваем количество массивов и снова тестируем.
const N = 10
func BenchmarkTwoSum1(b *testing.B) {
nums:=[]int{}
for i:=0;i<N;i++{
nums=append(nums,rand.Int())
}
nums=append( nums,7,2)
b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum1(nums,9)
}
}
func BenchmarkTwoSum2(b *testing.B) {
nums:=[]int{}
for i:=0;i<N;i++{
nums=append(nums,rand.Int())
}
nums=append( nums,7,2)
b.ResetTimer()
for i:=0;i<b.N;i++{
TwoSum2(nums,9)
}
}
Внимательно глядя на приведенный выше код, я использую метод автоматической случайной генерации элементов массива, но для обеспечения ответа последние две цифры массива по-прежнему7,2.
Сначала проверьте случай, когда размер массива равен 10.
BenchmarkTwoSum1-8 20000000 73.3 ns/op 16 B/op 1 allocs/op
BenchmarkTwoSum2-8 2000000 660 ns/op 318 B/op 2 allocs/op
10 элементов, метод грубой силы работает в 10 раз быстрее, чем метод хеширования.
Продолжайте корректировать размер массива до 50 и напрямую изменять константуNЧто ж, проверим случай с 50 элементами.
BenchmarkTwoSum1-8 2000000 984 ns/op 16 B/op 1 allocs/op
BenchmarkTwoSum2-8 500000 3200 ns/op 1451 B/op 6 allocs/op
По мере увеличения размера массива начинают проявляться преимущества хеширования, и при 50 элементах массива разница составляет всего 4 раза.
Начиная с увеличения размера массива, у меня на компе при размере массива 300 два завязаны и производительность одинаковая.
При размере массива 1000 производительность хэширования уже в 4 раза выше, чем у перебора, и наоборот.
При размере массива 10000 производительность хеш-метода уже в 20 раз выше, чем у метода полного перебора.Тестовые данные следующие:
BenchmarkTwoSum1-8 100 21685955 ns/op 16 B/op 1 allocs/op
BenchmarkTwoSum2-8 2000 641821 ns/op 322237 B/op 12 allocs/op
По контрольным данным, чем больше массив, тем больше времени занимает каждая операция, но время, затрачиваемое методом грубой силы, слишком велико, что приводит к низкой производительности.
Из данных также видно, что метод хэширования — это способ замены пространства на время, а занимаемая память и ее распределение относительно велики.
резюме
Из этого теста и анализа производительности не существует оптимального алгоритма, есть только наиболее подходящий.
Если в вашем массиве меньше элементов, то вам больше подходит алгоритм полного перебора. Если элементы массива очень большие, лучше использовать алгоритм хеширования.
Следовательно, в соответствии с реальной ситуацией в нашей собственной системе мы можем выбрать соответствующий алгоритм, например, динамическую оценку размера массива и использование различных алгоритмов для достижения максимальной производительности.
Эта статья является оригинальной статьей, перепечатайте ее и укажите источник: «Всегда есть плохие люди, которые удаляют мое исходное описание, когда берут статью». Добро пожаловать, чтобы отсканировать код и обратить внимание на общедоступную учетную запись.
flysnow_orgили сайтwww.flysnow.org/, и впервые прочитал последующие замечательные статьи. «Замечания против гнилых людей **...&*￥» Если вы считаете, что это хорошо, поделитесь им в кругу друзей, спасибо за вашу поддержку.