Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.92/133: Рейтинг темы: голосов - 133, средняя оценка - 4.92
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5

Коллекция без дубликатов

21.06.2012, 02:49. Показов 26275. Ответов 42
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте. Возник вопрос: мне нужно сделать коллекцию (т.е. динамический массив), но в нем не должно содержаться дубликатов, потому что их накапливается очень много и начинает ругаться на недостаток памяти. Для ликвидации этого решил сделать не List<Point>, а SortedSet<Point>, но тогда он начинает ругаться
По крайней мере в одном объекте должен быть реализован интерфейс IComparable.
Пробовал сделать наследника public class myPoint :IComparable<myPoint>, но тоже фигню какую-то сделал. Может есть какой-то способ проще, ну или просто написать интерфейс сравнения без написания отдельного класса как-то можно?
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
21.06.2012, 02:49
Ответы с готовыми решениями:

Сохранение без дубликатов
При сохранении надо поставить проверку, имеется ли в файле строки, которые будут сохранены. Сохранение происходит из listBox. string...

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

Поиск дубликатов без LINQ
Есть список объектов класса Class1. public class Class1 { public int Num; //номер по порядку public string ID;...

42
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
23.06.2012, 14:43  [ТС]
Студворк — интернет-сервис помощи студентам
kolorotur, нет, там я просто ставил условие, элементы там вообще никак не сортировались. Во втором случае да, у меня уже n^2/2; потому что сначала сравниваем с одним, потом с двумя, и только в конце сравниваем с n.
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
23.06.2012, 15:04
Tessen, покажите пожалуйсте код, где происходит сравнивание, а то не совсем понятно о каких замерах идет речь.

Добавлено через 34 секунды
Psilon, так а чем тот же Distinct или хэш не устраивает? Всяко ведь быстрее.
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
23.06.2012, 15:10  [ТС]
kolorotur, не умею им пользоваться, вот что. Я спросил, как можно было бы с ним реализовать, но никто мне не ответил.

Еще раз: имеется точка. Она преобразуется в цикле 10 раз, записывается в новый массив. Затем каждая из этих точек преобразуется 10 раз, получаем 100 точек. Делаем столько итераций, сколько нужно пользователю, хотя фактически больше 5 прироста не дает. Естественно, если точка уже один раз была обработана, то второй раз крутить 10 раз её не надо, потому что т.к. преобразование одно и то же, то мы получим тот же результат, который уже есть.

Как реализовать я придумал. Как реализовать оптимально я не знаю. Может, подскажете?
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
23.06.2012, 15:21
Psilon, несколько вопросов для уточнения:

Цитата Сообщение от Psilon Посмотреть сообщение
имеется точка.
Работа алгоритма всегда начинается с одной точки?

Цитата Сообщение от Psilon Посмотреть сообщение
Она преобразуется в цикле 10 раз, записывается в новый массив.
То есть в массив записываются только преобразования? Изначальная точка выбрасывается?

Цитата Сообщение от Psilon Посмотреть сообщение
если точка уже один раз была обработана, то второй раз крутить 10 раз её не надо, потому что т.к. преобразование одно и то же, то мы получим тот же результат, который уже есть.
Означает ли это, что если в ходе преобразования некой точки получился результат, координаты которого равны ранее полученным путем преобразования другой точки, то этот результат отбрасывается?
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
23.06.2012, 15:26  [ТС]
kolorotur,
Работа алгоритма всегда начинается с одной точки?
Да
То есть в массив записываются только преобразования? Изначальная точка выбрасывается?
Изначальная точка в итоге все равно получится преобразованием одной из последующих. Поэтому можно её откинуть. Это и происходит в цикле преобразования точки
C#
1
2
3
4
5
6
for (int j = 0; j < 10; j++)
{                        
   x = Convert.ToInt32(C[j, 0] * point.X + C[j, 1] * point.Y + C[j, 4]);
   y = Convert.ToInt32(C[j, 2] * point.X + C[j, 3] * point.Y + C[j, 5]);
   templist.Add(new Point(x, y));
}
x,y - координаты новой точки.
Означает ли это, что если в ходе преобразования некой точки получился результат, координаты которого равны ранее полученным путем преобразования другой точки, то этот результат отбрасывается?
Да, итоговая коллекция не должна содержать одинаковых точек. Вот код (возможно, медленный, но рабочий):
Вложения
Тип файла: rar FractalMAI.rar (611.4 Кб, 7 просмотров)
0
713 / 680 / 126
Регистрация: 30.03.2012
Сообщений: 1,124
23.06.2012, 15:47
Цитата Сообщение от kolorotur Посмотреть сообщение
Tessen, покажите пожалуйсте код, где происходит сравнивание, а то не совсем понятно о каких замерах идет речь.
так вот же он, в конце 1 страницы

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    var l1 = new List<int>();
            var l2 = new List<int>();
            var l3 = new List<int>();
            for (int i = 0; i < 500000; i++)
            {
                l1.Add(i);
                l2.Add(500000+i);
            }
            var sw = new Stopwatch();
            sw.Start();
            var hash = new HashSet<int>(l1);
            foreach (var x in l1)
                if (hash.Contains(x)) l3.Add(x);
            sw.Stop();
            var sw2 = new Stopwatch();
            l3 = new List<int>();
            l3.AddRange(l1);
            l3.AddRange(l2);
            sw2.Start();
            var l4 = new List<int>(l3.Distinct());
            sw2.Stop();
            Console.WriteLine(sw2.ElapsedMilliseconds+"\n"+sw.ElapsedMilliseconds);
            Console.ReadKey();
данный код показывает у меня выполнение sw2 - 40-45 мс
sw1 - 70-75
если я изменяю цикл создания листов так:
C#
1
2
3
4
5
            for (int i = 0; i < 500000; i++)
            {
                l1.Add(i);
                l2.Add(i);
            }
т.е. они становятся одинаковыми - sw1 становится районе 40-48 мс, sw2 не меняется

не понимаю почему так?
0
101 / 101 / 12
Регистрация: 21.11.2011
Сообщений: 169
23.06.2012, 16:24
Tessen, в чем вообще смысл сравнения времени даже не разных реализаций, а вообще разных алгоритмов?
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
23.06.2012, 18:42
Цитата Сообщение от Tessen Посмотреть сообщение
так вот же он, в конце 1 страницы
Ну просто выше по теме было высказано несколько комментариев по этому поводу, потому мне подумалось, что его как-то переписали.

Цитата Сообщение от Tessen Посмотреть сообщение
данный код показывает у меня выполнение sw2 - 40-45 мс
sw1 - 70-75
Как раз наоборот - "ручной" метод будет работать быстрее, чем тот, который с Distinct. У вас же первой строчкой выводится результат sw2 (который медленнее), а второй - sw.

Цитата Сообщение от Tessen Посмотреть сообщение
т.е. они становятся одинаковыми - sw1 становится районе 40-48 мс, sw2 не меняется
не понимаю почему так?
У вас в первом методе еще и алгоритм неправильный: вы хэшируете первый список, а потом по хэшу ищите элементы первого же списка. А надо бы второго.

Цитата Сообщение от hiddentool Посмотреть сообщение
в чем вообще смысл сравнения времени даже не разных реализаций, а вообще разных алгоритмов?
В сравнении их (алгоритмов) эффективности.
1
101 / 101 / 12
Регистрация: 21.11.2011
Сообщений: 169
23.06.2012, 19:53
Цитата Сообщение от kolorotur Посмотреть сообщение
В сравнении их (алгоритмов) эффективности.
это понятно, но сравнивать же нужно алгоритмы которые решают одну и ту же задачу,а сейчас упорно сравнивается скорость объединения со скоростью пересечения. Так можно сравнивать эффективность сложения с умножением, но в чем смысл этого действа, если это разные алгоритмы и заменить один другим все равно нельзя?
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
23.06.2012, 22:11  [ТС]
kolorotur, ну так, есть варианты?
0
101 / 101 / 12
Регистрация: 21.11.2011
Сообщений: 169
23.06.2012, 22:52
Цитата Сообщение от Psilon Посмотреть сообщение
есть варианты?
объявление
C#
1
HashSet<Point> list = new HashSet<Point>(); // SortedSet<Point> list = new SortedSet<Point>(new ComparePoints());
и замена
C#
1
SortedSet<Point> templist = new SortedSet<Point>(new ComparePoints());
на
C#
1
HashSet<Point> templist = new HashSet<Point>();
даст почти двухкратный прирост скорости в методе paintButton_Click
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
23.06.2012, 23:14  [ТС]
hiddentool, а за счет чего это ускорение? Он не упорядочивает структуру, а просто проверяет, нет ли её внутри, но все равно непонятна такая большая разница... )) В принципе вы правы, теперь 17-20 мс вместо 28-33
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
23.06.2012, 23:21
Цитата Сообщение от hiddentool Посмотреть сообщение
сравнивать же нужно алгоритмы которые решают одну и ту же задачу,а сейчас упорно сравнивается скорость объединения со скоростью пересечения.
Кстати да, тут вы правы - этот момент я просмотрел.
Во втором варианте ищутся уникальные элементы из обеих коллекций, а в первом - элементы из первой коллекции, которых нет во второй коллекции.

Цитата Сообщение от Psilon Посмотреть сообщение
ну так, есть варианты?
Ой, прошу прощения. Денек сегодня больно резвый был - отвечал как попало
Как предложили выше - замените SortedList на HashSet (сортировка вам ни к чему) и не создавайте новый список после каждой обработки - лучше просто не добавляйте уже имеющиеся в коллекции элементы. Сэкономите на памяти.
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
23.06.2012, 23:31  [ТС]
Цитата Сообщение от kolorotur Посмотреть сообщение
Ой, прошу прощения. Денек сегодня больно резвый был - отвечал как попало
Как предложили выше - замените SortedList на HashSet (сортировка вам ни к чему) и не создавайте новый список после каждой обработки - лучше просто не добавляйте уже имеющиеся в коллекции элементы. Сэкономите на памяти.
Хм, я думал, они автоматически удаляются при выходе за границу видимости. Тогда конечно стоит создать только один список

Кстати, после этого перестала работать операция
C#
1
list = templist
Если в цикле поставить templist.Clear(); то после первого же обнуления обнуляется и наш list. Если обнуление не ставить, то он ругается в foreach, что "коллекция была изменена".
Видимо, он копирует ссылку списка на временный список, а не сами значения...
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
23.06.2012, 23:37
Цитата Сообщение от Psilon Посмотреть сообщение
я думал, они автоматически удаляются при выходе за границу видимости.
Удаляются, но, скажем так, "рано или поздно". То есть когда до них сборщик доберется.
А до тех пор будут болтаться в памяти, как известная субстанция в прорубе.


Цитата Сообщение от Psilon Посмотреть сообщение
Кстати, после этого перестала работать операция list = templist
Видимо, он копирует ссылку списка на временный список, а не сами значения...
В смысле перестала работать?
И да, происходит присваивание ссылки, а не копирование значений.
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
23.06.2012, 23:43  [ТС]
kolorotur, в общем, ценой лишних 1мс работы получаем лишний 1мб памяти при том накликивании, о котором я в другой теме говорил (теперь не на 14.5 застревает, а на 13.5 )
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
23.06.2012, 23:55
Psilon, так покажите обновленный код, а то вентилятор топлива просит
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
24.06.2012, 00:15  [ТС]
Как можно увидеть, я свел появление новых переменных к минимуму, и все равно память с 10 до 13 растет (примерно по 200кб за нажатие на кнопку).
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
using System;
using System.Drawing;
using System.Windows.Forms;
using System.Collections.Generic;
 
 
 
 
namespace WindowsFormsApplication1
{
    public partial class MainForm : Form
    {
        internal static double[,] A, C; //Исходный и результативный массив
        internal static bool a, c;
        double[] D; //Массив определителей
        int[] omega = new int[2];
        HashSet<Point> list = new HashSet<Point>();
        bool clearPicture = false;
        const int m = 100;
 
        public MainForm()
        {
            InitializeComponent();
        }
 
        private void InitializeMatrix()
        {
            A = new double[,] {   {0,  0.25,  0.25,  0,  0,  0},
                                {0.125,  0,  -0.1875, 0.25,0.25,0.75},
                                {0.125,  0,  0.1875, 0.25,0.75,0},
                                {0,  0.25,  0.25,  0,  1.25,  0},
                                {0.15625,0,0.1875,0.25,1.5,0},
                                {0.15625,0,-0.1875,0.25,2.125,0.75},
                                {0,  0.25,  0.25,  0,  2.75,  0},
                                {0.1875,0,0.1875,0.25,3,0},
                                {0,  0.25,  0.25,  0,  3.75,  0},
                                {0.125,  0,  0, 0.125, 1.875, 0.325}};
            C = new double[10, 6];
            D = new double[10];
            for (int i = 0; i < 10; i++)
            {
                D[i] = Math.Abs(A[i, 0] * A[i, 3] - A[i, 1] * A[i, 2]);
            }
            foreach (double var in D)
            {
                detLabel.Text += var + "\n";
            }
        }
 
 
        private void Recalculate() // Метод пересчета матрицы C и омег
        {
            omega[0] = Convert.ToInt32(omega0TextBox.Text);
            omega[1] = Convert.ToInt32(omega1TextBox.Text);            
            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 4; j++)
                    C[i, j] = j == 0 || j == 3 ? A[i, j] : -A[i, j];
                C[i, 4] = m * A[i, 4] + (1 - A[i, 0]) * omega[0] + A[i, 1] * omega[1];
                C[i, 5] = -m * A[i, 5] + A[i, 2] * omega[0] + (1 - A[i, 3]) * omega[1];
            }            
        }
 
        private void Form1_Load(object sender, EventArgs e)
        {
            a = c = false;
            InitializeMatrix();
            Recalculate();            
            DoubleBuffered = true;
        }
 
        private void paintButton_Click(object sender, EventArgs e) // Метод формирования массива пикселей
        {            
            clearPicture = false;
            Recalculate();
            int x, y; // Координаты точки
            int l = (int)numericUpDown1.Value; // Количество итераций
 
            // Расчет
            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            list.Clear();
            HashSet<Point> templist = new HashSet<Point>();
            list.Add(new Point(omega[0],omega[1])); // координаты начальной точки
            for (int i = 0; i < l; i++)
            {                
                foreach (Point point in list)
                    for (int j = 0; j < 10; j++)
                    {                        
                        x = Convert.ToInt32(C[j, 0] * point.X + C[j, 1] * point.Y + C[j, 4]);
                        y = Convert.ToInt32(C[j, 2] * point.X + C[j, 3] * point.Y + C[j, 5]);
                        templist.Add(new Point(x, y));
                    }
                foreach (var Var in templist) 
                    list.Add(Var);
            }
            MessageBox.Show(sw.ElapsedMilliseconds.ToString());
            pictureBox1.Invalidate();
        }
 
        private void pictureBox1_Paint(object sender, PaintEventArgs e)
        {
            // вывод информации
            if (clearPicture)
                e.Graphics.FillRectangle(Brushes.White, pictureBox1.Left, pictureBox1.Top, pictureBox1.Width, pictureBox1.Height);
            else
                foreach (Point p in list)
                    e.Graphics.DrawRectangle(Pens.Green, p.X, p.Y, 1, 1);
        }
 
        private void clearButton_Click(object sender, EventArgs e)
        {
            clearPicture = true;
            pictureBox1.Refresh();
        }
    }
}
Добавлено через 10 минут
И еще вопрос: в чем разница между методами Invalidate и Refresh для графических компонент?
0
101 / 101 / 12
Регистрация: 21.11.2011
Сообщений: 169
24.06.2012, 09:35
Цитата Сообщение от Psilon Посмотреть сообщение
а за счет чего это ускорение? Он не упорядочивает структуру, а просто проверяет
именно из-за этого. поддержание упорядоченной структуры гораздо затратнее по ресурсам.
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
24.06.2012, 12:30  [ТС]
hiddentool, логически это можно понять, но по сути? Он все равно проходит от начала до конца проверяя, нет ли в нем уже этой точки, вопрос только в том, что в одном случае он впихнет её в середину (а-ля очередь с приоритетом), а в другом просто в конец. Но и в том и в другом случае придется 4 указателя изменять: два указателя соседних элементов и 2 указателя самого элемента. Так почему же быстрее?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
24.06.2012, 12:30

При вводе в консоли "delete" записать новый массив без дубликатов
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { ...

Раскрывающийся список без дубликатов
Здравствуйте, не подскажите как мне решить вопрос: есть список городов но в нем есть повторы, как мне сделать раскрывающийся список, чтобы...

Добавить запись без дубликатов
Нужно составить SQL запрос: Добавить 1 запись только если этой записи не существует в таблицу CATEGORY. Сейчас у меня так: INSERT...

Объединение без удаления дубликатов
В Linq есть метод Union-для обьединения резултатов двух или более операторов Linq с исключением повторяющихся строк.А есть ли метод для...

Получение записей с сервиса без дубликатов
Беру информацию о аэропортах определенной страны с webservicex, но у них там все данные дублируются, как мне без дубликатов информацию...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Сезонность и суточность закисления почв
anaschu 04.07.2026
200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле?
kumehtar 03.07.2026
Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo
anaschu 03.07.2026
Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux
dcc0 02.07.2026
Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .
Сам себя обучал rest api
anaschu 02.07.2026
Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .
rest api anylogic - выполнение модели на своём русском сайте
anaschu 02.07.2026
Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат
kumehtar 02.07.2026
Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .
Krabik для WoW 3.3.5a, многоязычный
AmbA 02.07.2026
Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru