Форум русскоязычного сообщества Ubuntu


Увидели сообщение с непонятной ссылкой, спам, непристойность или оскорбление?
Воспользуйтесь ссылкой «Сообщить модератору» рядом с сообщением!

Автор Тема: Помогите оптимизировать код  (Прочитано 721 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Помогите оптимизировать код
« : 01 Июнь 2014, 22:31:09 »
Задача: сдвинуть элементы массива стоящие до первого определенного заранее объекта элемента вперед, сам объект удаляется, остальные элементы копируются с текущим номером.
Пример работыВход  1, 4, 4, 1, 0, 0, 0, 0
Выход 0, 1, 4, 1, 0, 0, 0, 0
Первый элемент - ноль по дефолту. Моя реализация
Код: Genie
  1. //Аналог main в других ЯП
  2. init
  3.         //Инициализация массива
  4.         arr : array of int = {1, 4, 4, 1, 0, 0, 0, 0}
  5.         //Создаем еще одну копию массива
  6.         var temp = new array of int[arr.length]
  7.         var n = 0
  8.         var sdvigat = true
  9.         var uzhe = false
  10.         while n < arr.length
  11.                 var t = arr[n]
  12.                 if sdvigat
  13.                         temp[++n] = t
  14.                 else
  15.                         temp[n] = t
  16.                         n++
  17.                 if uzhe
  18.                         uzhe = false
  19.                         sdvigat = false
  20.                 if arr[n] is 4 do uzhe = true
  21.         //Распечатываем значения массива
  22.         arr = temp
  23.         for i in arr
  24.                 //Подстановка переменной i
  25.                 print @"$i"
Если можно оптимизировать - подскажите как.
PS компилятор valac, как поставить смотрите здесь
« Последнее редактирование: 02 Июнь 2014, 00:15:09 от alsoijw »
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12065
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #1 : 02 Июнь 2014, 14:34:53 »
Я бы в питоне сделал так:


Код: Python
  1.  
  2.   a = [1, 4, 4, 1, 0, 0, 0, 0] # первичный массив
  3.   print(a)                     # распечатаем его
  4.   n = 2                        # позиция удаляемого эелемента (индексация с 0)
  5.   i = n                        # начальная позиция для сдвига
  6.   while i > 0:                 # сдвигаем все до первой (0-вой) позиции
  7.     a[i] = a[i-1]              # сдвиг
  8.     i-=1                       # переходим к следующему элементу
  9.   a[0] = 0                     # прописываем заполнитель
  10.   print(a)                     # распечатаем результат
  11.  

Цитировать
[1, 4, 4, 1, 0, 0, 0, 0]
[0, 1, 4, 4, 0, 0, 0, 0]

Суть действа:
1. Раз уж мы смещаем более левые элементы направо - то идти надо не слева-направо, а с права налево (тогда не нужен промежуточный массив, а делать можно сразу в первичном).
2. Обходить весь массив - нет смысла т.к. в нем затрагиваются элементы от второго до n-ного + первый всегда обнуляется. Остальные лучше просто не трогать.
3. В цикле имеет смысл делать только перенос элементов, а добавление дефолтного значения - операция безусловная.


(Нажмите, чтобы показать/скрыть)



 
« Последнее редактирование: 02 Июнь 2014, 15:23:28 от Sly_tom_cat »
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #2 : 02 Июнь 2014, 15:11:00 »
Sly_tom_cat, спасибо, сейчас перепишу.
PS Я не студент, а школьник самоучка.
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12065
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #3 : 02 Июнь 2014, 15:15:38 »
(Нажмите, чтобы показать/скрыть)


Да, погнавшись за оптимизацией я сам чутка напортачил  :-[ провильный код такой:
 
Код: Python
  1. a = [1, 4, 4, 1, 0, 0, 0, 0]
  2.   print(a)
  3.   n = 2
  4.   i = n -1
  5.   while i > 0:
  6.     a[i] = a[i-1]
  7.     i-=1
  8.   a[i] = 0
  9.   print(a)
Цитировать
[1, 4, 4, 1, 0, 0, 0, 0]
[0, 1, 4, 1, 0, 0, 0, 0]

Исправлена 4-я строчка.

Но с индексацией, по любому придется адаптировать под другой язык.
« Последнее редактирование: 02 Июнь 2014, 15:21:57 от Sly_tom_cat »
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #4 : 02 Июнь 2014, 15:32:41 »
Переделал. Какова оценка?
Код: Genie
  1. init
  2.         arr : array of int = {1, 4, 4, 1, 0, 0, 0, 0}
  3.         i : int
  4.         for i = 0 to arr.length
  5.                 if arr[i] is 4 do break
  6.         while i > 0 do arr[i] = arr[--i]
  7.         for n in arr
  8.                 print @"$n"

Пользователь решил продолжить мысль 02 Июнь 2014, 15:33:55:
Да, кстати номер элемента для удаления нам заранее не известен.

Пользователь решил продолжить мысль 02 Июнь 2014, 15:42:59:
Правда первый элемент остается с начальным значением, ну ладно, все равно буду присваивать случайное число. Это я немного не правильно сформулировал условие.
« Последнее редактирование: 02 Июнь 2014, 15:42:59 от alsoijw »
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12065
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #5 : 02 Июнь 2014, 15:45:43 »
Ничего не понятно по условию - что значит "номер элемента для удаления нам заранее не известен" - что известно - сам элемент (значение) которое удалять? если он встречается неоднократно - то какой?

Допустим удаляем 4 из массива [1, 1, 4, 1, 4, 3, 1, 4, 1, 0] - какую именно 4-ку удалять? 1-ю слева, 1-ю справа, ... все?
« Последнее редактирование: 02 Июнь 2014, 15:53:00 от Sly_tom_cat »
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #6 : 02 Июнь 2014, 15:52:33 »
Нам известно значение элемента. Удаляется самое первое.
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12065
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #7 : 02 Июнь 2014, 15:53:15 »
alsoijw, первое с какого края?
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #8 : 02 Июнь 2014, 15:57:56 »
С наименьшим индексом.
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12065
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #9 : 02 Июнь 2014, 18:37:17 »
Ок, но код должен содержать еще одну проверку.
У вас сейчас завершение цикла на массиве не содержащем четверки, закончится на индексе = arr.lenght и далее безусловно запускается сдвиг.

Т.е. обработки ситуации когда элемент не найден - просто нет.
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #10 : 02 Июнь 2014, 19:20:58 »
Не подумал про проверку. Вылетает красноречиво.1: malloc.c:2372: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.Новый вариант
Код: Genie
  1. init
  2.         arr : array of int = {1, 2, 3, 5, 6, 7, 8, 9}
  3.         i : int
  4.         for i = 0 to arr.length
  5.                 if arr[i] is 4 do break
  6.         if i > arr.length
  7.                 i--
  8.         while i > 0 do arr[i] = arr[--i]
  9.         for n in arr
  10.                 print @"$n"
Работает как и надо. 1
1
2
3
5
6
7
8
Первый элемент все равно заменять, но это уже другая история.
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн Sly_tom_cat

  • Don't worry, be happy!
  • Заслуженный пользователь
  • Старожил
  • *
  • Сообщений: 12065
  • Xubuntu 20.04 (64bit)
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #11 : 02 Июнь 2014, 23:21:24 »
Опять какое-то новое условие... :idiot2:

Получается (по коду) так:
1. Найти и удалить первый с начала (слева) элемент со значением X,
2. Элементы начиная с первого сдвинуть вправо на 1 до места удаления.
3. Если элемент не найден - сдвинуть все элементы (удаляется последний)
4. Первый элемент заполнить заполнителем Y.

Если условия такие - то код похож на правду. И вполне оптимален.
Индикатор для Yandex-Disk: https://forum.ubuntu.ru/index.php?topic=241992
UEFI-Boot - грузимся без загрузчика: http://help.ubuntu.ru/wiki/uefiboot

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #12 : 03 Июнь 2014, 09:13:24 »
Sly_tom_cat, ну да как то так.
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

Оффлайн Phlya

  • Старожил
  • *
  • Сообщений: 2219
  • Фля, Цыганский барон, Винни Пух
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #13 : 03 Июнь 2014, 10:27:00 »
Я бы в питоне сделал так:


Код: Python
  1.  
  2.   a = [1, 4, 4, 1, 0, 0, 0, 0] # первичный массив
  3.   print(a)                     # распечатаем его
  4.   n = 2                        # позиция удаляемого эелемента (индексация с 0)
  5.   i = n                        # начальная позиция для сдвига
  6.   while i > 0:                 # сдвигаем все до первой (0-вой) позиции
  7.     a[i] = a[i-1]              # сдвиг
  8.     i-=1                       # переходим к следующему элементу
  9.   a[0] = 0                     # прописываем заполнитель
  10.   print(a)                     # распечатаем результат
  11.  

Цитировать
[1, 4, 4, 1, 0, 0, 0, 0]
[0, 1, 4, 4, 0, 0, 0, 0]

Красиво!
Ubuntu 14.04 (Unity), MSI GE40

Оффлайн alsoijw

  • Автор темы
  • Старожил
  • *
  • Сообщений: 4073
  • Fedora 25 GNOME 3 amd64
    • Просмотр профиля
Re: Помогите оптимизировать код
« Ответ #14 : 03 Июнь 2014, 10:32:18 »
Phlya, это вообще к чему?
Мало видеть нам начало - надо видеть и конец. Если видишь ты создание - значит где-то есть ТВОРЕЦ
Многие жалуются: геометрия в жизни не пригодилась. Ямб от хорея им приходится отличать ежедневно?

 

Страница сгенерирована за 0.223 секунд. Запросов: 25.