Оптимизация метода сортировки

@I32M6 · Регистрация: 17.05.2020

Студворк — интернет-сервис помощи студентам

Всем привет. Есть задание: написать и продемонстрировать сортировку Шелла с различными длинами промежутков.(https://en.wikipedia.org/wiki/Shellsort - здесь в gap Sequence можно посмотреть).
Реализовал пару сортировок Шелла, написал реализацию под JChart, но возникла одна проблема. Есть выбор длины промежутка Хиббарда с О^3/2.Реализация работает то правильно.Но данный метод работает хуже, чем другой метод с О².
Подозреваю, что дело в том, что здесь используются Math.pow и Math.log, они ведь много жрут, по идее. Но я не знаю, как их заменить.Или может у меня ошибка в реализации... Можете помочь с этим?

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void sortHibbard(Integer[] array) {//Хиббард
        int temp;
        int k = (int) (Math.log(array.length + 1) / Math.log(2));
        int gap = (int) (Math.pow(2, k) - 1);
 
        while (gap > 0) {
            for (int g = 0; g < gap; g++) {
                for (int d = g + gap; d < array.length; d = d + gap) {
                    for (int i = d; i - gap >= 0; i = i - gap) {
                        if (array[i - gap] <= (array[i])) {
                            break;
                        }
                        temp = array[i];
                        array[i] = array[i - gap];
                        array[i - gap] = temp;
                    }
                }
            }
            k--;
            gap = (int) (Math.pow(2, k) - 1);
        }
    }

@xoraxax · 17.06.2020, 13:54

Сообщение от I32M6

Integer[]

int[] и убираем лишние боксинги?

Сообщение от I32M6

Но данный метод работает хуже, чем другой метод с О2.

как определил? что, конкретно, значит "хуже"?

Сообщение от I32M6

Но я не знаю, как их заменить

ты считаешь, что можешь написать логарифм или степень лучше, чем это сделано в яве?

@I32M6 · 17.06.2020, 16:26 **[ТС]**

Сообщение от xoraxax

int[] и убираем лишние боксинги?

Integer нужен для того, чтобы работало в JChart(библиотека для отображения графиков ) А вообще, это может сильно влиять на производительность?(Хотя в любом случае, у меня везде Integer[], так что ...)

Сообщение от xoraxax

как определил? что, конкретно, значит "хуже"?

График быстродействия у данной функции самый плохой, хотя должен быть получше, чем стандартная сортировка Шелла и наравне с другими, которые я реализовал(если смотреть по О-символике).

Сообщение от xoraxax

ты считаешь, что можешь написать логарифм или степень лучше, чем это сделано в яве?

Я не сказал, что могу))). Я просто спросил, возможно ли как-то заменить. Препод что-то говорил про побитовый сдвиг, но я прост не очень понимаю, как что-то с ним сделать сделать.

@alecss131 · 17.06.2020, 16:31

Ну как бы Integer это объект (не знаю скок весит, но точно больше int) а int примитив размером 4 байта

Добавлено через 1 минуту
хотя вес тут скорее дело десятое, но имхо с примитивами должно быть получше чем с объектами

@I32M6 · 17.06.2020, 16:32 **[ТС]**

Вот так это выглядит, но Хиббард должен работать намного лучше...

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

@alecss131 Модератор 2881 / 1387 / 411 Регистрация: 11.08.2017 Сообщений: 4,428 Записей в блоге: 2
	17.06.2020, 16:31
	Ну как бы Integer это объект (не знаю скок весит, но точно больше int) а int примитив размером 4 байта Добавлено через 1 минуту хотя вес тут скорее дело десятое, но имхо с примитивами должно быть получше чем с объектами 1

@I32M6 5 / 4 / 1 Регистрация: 17.05.2020 Сообщений: 17
	17.06.2020, 16:32 [ТС]
	Вот так это выглядит, но Хиббард должен работать намного лучше... Миниатюры 0