Заблокирован
1

В классе Array есть метод Sort. Можете ли вы улучшить этот метод, если значения в массиве часто повторяются

24.06.2014, 16:17. Показов 1392. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Как то проходил собеседование в одну конторку.Задали логическую задачку которую не смог решить.Может кто-нить знает .
Вот задача:
В классе Array есть метод Sort.Можете ли вы улучшить этот метод ,если значения в массиве часто повторяются.
Вот такая задачка.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.06.2014, 16:17
Ответы с готовыми решениями:

Array.Sort() Какие параметры передать в этот метод?
Array.Sort(); Какие параметры передать в этод метод, чтобы масив отсортироватся не по возрозтанию,...

В классе OnlyData написать метод, который выводит значение переменной i и вызвать этот метод в том же классе
Я конечно понимаю, что задача оч простая, но все же. В классе OnlyData нужно написать метод,...

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

Обязательно ли описывать функцию с override, если в базовом классе уже есть метод с virtual?
Здравствуйте, хотел узнать обязательно ли описывать функцию с override если к примеру в базовом...

7
484 / 439 / 123
Регистрация: 05.01.2010
Сообщений: 1,848
24.06.2014, 16:41 2
навскидку. если не ошибаюсь, Array.Sort() реализует QuickSort. по сути, надо знать разные методы сортировки и их особенности. явно какой то метод сортировки при наличии одинаковых значений в массиве сортирует быстрее. собственно надо было по идее его и реализовтаь
0
Эксперт .NET
17678 / 12864 / 3365
Регистрация: 17.09.2011
Сообщений: 21,132
25.06.2014, 13:03 3
Цитата Сообщение от valera_21 Посмотреть сообщение
если не ошибаюсь, Array.Sort() реализует QuickSort
Там используется комбинированный метод в зависимости от размера массива и глубины рекурсии при быстрой сортировке.
Но по умолчанию — да, используется быстрая сортировка.

ts-alan, если массив состоит из небольшого количества часто повторяющихся элементов, то эффективнее будет сделать один полный обход массива чтобы выделить уникальные элементы и количество их повторений, потом отсортировать эти уникальные элементы (чем меньше массив, тем быстрее сортировка), после чего скопировать каждый из этих элементов необходимое количество раз в исходный массив в порядке возрастания.
1
Заблокирован
25.06.2014, 14:51  [ТС] 4
ts-alan, если массив состоит из небольшого количества часто повторяющихся элементов, то эффективнее будет сделать один полный обход массива чтобы выделить уникальные элементы и количество их повторений, потом отсортировать эти уникальные элементы (чем меньше массив, тем быстрее сортировка), после чего скопировать каждый из этих элементов необходимое количество раз в исходный массив в порядке возрастания.
Можно кодом показать. Ато как-то не сильно воспринимается.
0
Master of Orion
Эксперт .NET
6098 / 4954 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
25.06.2014, 18:07 5
Ну как-то так
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using System;
using System.Collections.Generic;
 
namespace ConsoleApplication34
{
    internal class Program
    {
 
        private static void Main(string[] args)
        {
            var random = new Random();
            int[] a = new int[100];
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = random.Next(10);
                Console.Write(a[i]);
            }
 
            Console.WriteLine();
            Console.WriteLine();
            FastSort(a);
 
            for (int i = 0; i < a.Length; i++)
            {
                Console.Write(a[i]);
            }
        }
 
        private static void FastSort<T>(T[] a)
        {
            var result = new SortedDictionary<T, int>();
            foreach (T t in a)
            {
                if (result.ContainsKey(t))
                    result[t]++;
                else
                    result.Add(t, 0);
            }
            int i = 0;
            foreach (var v in result)
            {
                for (int j = v.Value; j >= 0; j--)
                    a[i++] = v.Key;
            }
        }
    }
}
хотя уверен, что стандартный Sort все же быстрее

Добавлено через 2 минуты
kolorotur, там всегда используется Introsort сортировка, быстрая - только на небольшой глубине рекурсии, как часть этой Introsort
0
Эксперт .NET
17678 / 12864 / 3365
Регистрация: 17.09.2011
Сообщений: 21,132
25.06.2014, 18:16 6
Цитата Сообщение от Psilon Посмотреть сообщение
там всегда используется Introsort сортировка
Дык я про нее и говорил

Цитата Сообщение от Psilon Посмотреть сообщение
C#
1
result.Add(t, 0);
Наверное, все-таки единичку.
Или откат?!
0
Master of Orion
Эксперт .NET
6098 / 4954 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
25.06.2014, 18:21 7
kolorotur, компенсируется в цикле for (int j = v.Value; j >= 0; j--)

Добавлено через 55 секунд
Цитата Сообщение от kolorotur Посмотреть сообщение
Дык я про нее и говорил
тогда я не понял этой фразы:
Цитата Сообщение от kolorotur Посмотреть сообщение
Но по умолчанию — да, используется быстрая сортировка.
0
Эксперт .NET
17678 / 12864 / 3365
Регистрация: 17.09.2011
Сообщений: 21,132
25.06.2014, 18:36 8
Цитата Сообщение от Psilon Посмотреть сообщение
компенсируется в цикле
Ай, в разоблачительном угаре не дошел до цикла!

Цитата Сообщение от Psilon Посмотреть сообщение
тогда я не понял этой фразы
Когда-то давно копался в исходниках .NET и как раз смотрел код сортировки.
Из того, что запомнилось, там использовалось несколько алгоритмов: для небольших массивов то ли вставками, то ли слиянием, для остальных дефолтом быстрой с переходом в какой-то момент к сортировке кучей.
Возможно, это был код не от Array.Sort, а от какого-нибудь линковского OrderBy, сейчас уже не помню
1
25.06.2014, 18:36
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.06.2014, 18:36
Помогаю со студенческими работами здесь

Если асинхронные методы вызывают другой метод, то этот другой метод тоже должен быть async?
Есть несколько потоков, в которых асинхронные методы. Эти методы вызывают одну и ту же функцию....

Метод для поиска локального минимума в классе Array
Здравствуйте. Такая задача: Дан массив размера N. Найти номер его первого локального минимума...

Метод, который сортирует и печатает массив по длине строчки, без использования готовой функции Array.Sort
с готовой функцией как то проще а как можно реализовать без Array.Sort и Compare например дан...

В классе Array задайте метод add b , который будет добавлять к массиву почленно элементы массива...
Задание посвящено описанию вспомогательной функции. В классе Array задайте метод add b , который...

Как в классе Thread реализован вызов run(), если метод run() определён в АВТОРСКОМ классе?
И, следовательно, в классе Thread ничего не известно о вызове run? То есть, ребята, мне пришла в...

В классе Student определите метод InitAr (Метод должен быть статическим)
Здравствуйте. Помогите пожалуйста разобраться в задании: a. В классе Student определите метод...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru