BG Development


Страници: (2) [1] 2   ( Първото ново мнение ) Reply to this topicStart new topicStart Poll

> Как алгоритъмът да стане по-бърз?
cracker.
Публикувано на: 04-12-2023, 22:57
Quote Post



Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 26
Регистриран на: 13.11.23



Здравейте!

Начинът, по който решавам задачата, със сигурност е супер глупав, но толкова си мога за момента :д.

Условието е следното:
CODE

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
 # should be 6: [4, -1, 2, 1]
Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.


Решението ми минава всички тестове в платформата, но гърми за време когато размерът на листа е по-голям, сиреч само в този случай:
CODE
Should obtain correct maximum subarray sum in 10 random tests with array size 10000 <= size <= 20000 and with integer entries -100 <= n <= 100


CODE
def areAllNegative(my_list):
   for x in my_list:
       if x >= 0:
           return False
   return True
def max_sequence(my_list):
   if my_list is None or areAllNegative(my_list):
       return 0;
   max_sum = 0;
   for x in range(len(my_list)+1):
       for y in range(x+1,len(my_list)+1):
           if max_sum < sum(my_list[x:y]):
               max_sum = sum(my_list[x:y]);
   return max_sum;

Как да оптимизирам алгоритъма си, че да работи по-бързо?

След 12-тата секунда чудене, кодът не минава. 12000мс таван.

Благодаря ви предварително, лека вечер и всичко най-добро.

Това мнение е било редактирано от cracker. на 04-12-2023, 23:00
PMEmail Poster
Top
Bender++
Публикувано на: 04-12-2023, 23:38
Quote Post



Име:
Група: Потребител
Ранг: Редовен член

Мнения: 499
Регистриран на: 18.04.21



Това се решава с алгоритъма на Kadane:

CODE

pub fn max_sub_array(nums: Vec<i32>) -> i32 {
   if nums.is_empty() {
       return 0;
   }

   let mut best = nums[0];
   let mut sum = nums[0];

   nums.iter().skip(1).for_each(|&n| {
       if sum <= 0 {
           sum = n;
       } else {
           sum += n;
       }

       best = best.max(sum);
   });

   best
}


--------------------
Слава на Цар Путин! Долу украинските фашисти!
PMEmail Poster
Top
BIGBUGEX
Публикувано на: 05-12-2023, 00:14
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 1703
Регистриран на: 30.11.04



Като начало извикваш ненужно 2 пъти sum с едни същи параметри, което е излишно. Може да се направи с много по-малко операции ако си вършиш работата сам и не викаш sum. По метода на разклащането например. Първо проверяваш сумите от 1 елемент за макс като обхождаш масива до края. Следваща стъпка е проверка на сумите с 2 елемента, като се връщаш обхождайки към началото. И придвижваш сумата към началото като вадиш последния и добавяш новия първи елемент. Така вече имаш проверки на сумите от 2 елемента за макс. Стигнал си до началото и имаш сумата на първите 2 елемента. Добавяш третия и започваш да придвижваш сумата за 3 елемента към края. Тва разклащане е за да нямаш много пропуски при достъп от кеша.

Така бих го реализирал на С++. Но като се има предвид, че питон се интерпретира може да се окаже 100 пъти по-бавно.

Едит: По-добре виж на @Бендер решението.

Това мнение е било редактирано от BIGBUGEX на 05-12-2023, 00:19
PMEmail Poster
Top
SuN
Публикувано на: 05-12-2023, 11:24
Quote Post


Group Icon
Име:
Група: Администратор
Ранг: Почетен член

Мнения: 12666
Регистриран на: 27.01.05



Бендере, да го беше написал на С++, щеше да е по-четимо. Не знам откъде ги намирате тия измислени езици. Ето нещо близко до синтаксиса на Питон:

CODE
package main
import "fmt"
func main () {
      nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
      bestSum, currentSum := -200, 0
      for i := range nums {
            currentSum = max (nums[i], currentSum + nums[i])
            bestSum = max (bestSum, currentSum)
      }
      fmt.Println (bestSum)
}

Цялата програма е по-кратка от функцията ти. icon_smile.gif

Това мнение е било редактирано от SuN на 05-12-2023, 11:52


--------------------
Само аз не троля.
Всички коментари са плод на художествена измислица и нямат общо с действителни и недействителни лица, събития и факти.
PMEmail Poster
Top
cracker.
Публикувано на: 05-12-2023, 12:38
Quote Post



Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 26
Регистриран на: 13.11.23



Благодаря Ви!
Със сигурност функцията, проверяваща дали всички са негативни, е ненужна и има по-добър вариант, но закъснявам за работа (да изкараме некой бакшиш преди да ги обложат с данъци ;д) и не мога да я мисля сега.
Така минава:
CODE
def are_all_negative(my_list):
   for x in my_list:
       if x >= 0:
           return False;
   return True
def max_sequence(my_list):
   if my_list is None or are_all_negative(my_list):
       return 0;
   max_current = max_global = my_list[0];
   for i in range(1,len(my_list)):
       max_current = max(my_list[i], max_current + my_list[i]);
       if max_current > max_global:
           max_global = max_current;
   return max_global;


Живи и здрави.

п.с утрото е по-мъдро от вечерта.даже не знам кво съм очаквал с тея два нестед цикъла, хаха.
CODE
random tests with array size 10000 <= size <= 20000
тука е имало да си въртии и върти ;д.

Това мнение е било редактирано от cracker. на 05-12-2023, 12:58
PMEmail Poster
Top
relax4o
Публикувано на: 05-12-2023, 13:10
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2797
Регистриран на: 04.04.07



QUOTE (SuN @ 05-12-2023, 11:24)
Бендере, да го беше написал на С++, щеше да е по-четимо. Не знам откъде ги намирате тия измислени езици. Ето нещо близко до синтаксиса на Питон:

CODE
package main
import "fmt"
func main () {
      nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
      bestSum, currentSum := -200, 0
      for i := range nums {
            currentSum = max (nums[i], currentSum + nums[i])
            bestSum = max (bestSum, currentSum)
      }
      fmt.Println (bestSum)
}

Цялата програма е по-кратка от функцията ти. icon_smile.gif

Ти от кога стана Голанг-аджия?


--------------------
Бисери :D

QUOTE (oveRLuckEd)
Ползваш някоя нова версия на PHP, която е вече ооп ориентирана и заради това ти я изкарва тази грешка.


QUOTE (nbacool2)
Щом няма input полета, значи няма откъде да се направи SQL инжекция Very Happy
PM
Top
Bender++
Публикувано на: 05-12-2023, 13:51
Quote Post



Име:
Група: Потребител
Ранг: Редовен член

Мнения: 499
Регистриран на: 18.04.21



голанга е голямо дърво


--------------------
Слава на Цар Путин! Долу украинските фашисти!
PMEmail Poster
Top
relax4o
Публикувано на: 05-12-2023, 15:57
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2797
Регистриран на: 04.04.07



От всичките примери тук, между другото, Rust примера на Бендера е най-четим. Знаем, че Ръст може да стане много нечетим (то същото важи за C++), но Сънчо този път се хвана на най-простото парче код. icon_lol.gif


--------------------
Бисери :D

QUOTE (oveRLuckEd)
Ползваш някоя нова версия на PHP, която е вече ооп ориентирана и заради това ти я изкарва тази грешка.


QUOTE (nbacool2)
Щом няма input полета, значи няма откъде да се направи SQL инжекция Very Happy
PM
Top
SuN
Публикувано на: 05-12-2023, 22:27
Quote Post


Group Icon
Име:
Група: Администратор
Ранг: Почетен член

Мнения: 12666
Регистриран на: 27.01.05



QUOTE (relax4o @ 05-12-2023, 13:10)
QUOTE (SuN @ 05-12-2023, 11:24)
...

Ти от кога стана Голанг-аджия?

Флиртувам само с технологии за ремоте работа. Не съм се спрял на нещо конкретно.

QUOTE (Bender++)
голанга е голямо дърво

Изприщих се само като видях този пример:
CODE
       best = best.max(sum);

Викам си метод max на тип инт32 само някой джавар може да го кефи. Може да пробваш и Руби - там числата имат методи (стивито преди години беше много развълнувам от езика). icon_smile.gif


--------------------
Само аз не троля.
Всички коментари са плод на художествена измислица и нямат общо с действителни и недействителни лица, събития и факти.
PMEmail Poster
Top
Bender++
Публикувано на: 05-12-2023, 22:47
Quote Post



Име:
Група: Потребител
Ранг: Редовен член

Мнения: 499
Регистриран на: 18.04.21



Гото е много гадно, сега пиша на него и съм го намразил на макс. Примерно

CODE

// имаме някаква структура, без значение каква
type Shit struct{
 wtf int
}

// и искаме да проверим дали дадена инстанция е равна на дефолтната стойност (друго голямо дърво)

func shittyShit(){
//...

   if myVar == Shit{}{
       // do something stupid
   }

}


И капитан пайк ни удря с инструмента си (голанга, да не си помислите нещо друго) в челото. Горното няма да се компилира, защото ... само капитан Пайк знае защо. За да се компилира трябва да направим така:

CODE

   defaultShit := Shit{}
   if myVar == defaultShit{
       // do something stupid
   }


Гениално.


Всеки с поне малко усет, би се опитал да направи константа:
CODE

const defaultShit = Shit{}


обаче капитан Пайк, пак ни удря с инструмента в челото - константи могат да са само литерали, евалата


--------------------
Слава на Цар Путин! Долу украинските фашисти!
PMEmail Poster
Top
0 потребители преглеждат тази тема в момента (0 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Страници: (2) [1] 2  Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2019 | BG Development | All Rights Reserved
RSS 2.0