Как быстро проверить массив на наличие равных элементов

@Dennis Ritchie · Регистрация: 27.07.2014

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

Можно написать такую функцию:

C++
1
2
3
4
5
6
int busy(int j) {
    foreach (i; 0 .. j)
        if (a[i] == a[j])
            return 0;
    return 1;
}

Но меня интересует: есть ли в D уже готовые функции, которые возвращают 0/1 или индексы ~~равного элемента~~ одинаковых элементов массива.

@Ev_Hyper · 08.03.2015, 18:17

Сообщение от Dennis Ritchie

А вы продемонстрируйте, а я потом решу, что лучше использовать.

Dennis Ritchie, а самому открыть
http://dlang.org/
и посмотреть сложно? Вы же D - программист, а не я:

Java
1
2
3
4
5
6
7
8
9
10
11
import std.stdio;
import std.algorithm;
import std.range;
 
void main() {
 
    int[] array = [2, 3, 3, 4, 5 ];
    int index = 3;
 
    writeln(find((take(array,index)~drop(array,index+1)),4).length>0);
}

Code
1
false

http://ideone.com/pXEGVW

@Catstail · 08.03.2015, 19:50

Сообщение от Dennis Ritchie

Зато количество символов в записи метода поиска можно уменьшить

- не понял... Если задача формулируется так: найти индексы элементов массива, совпадающих с заданным числом (и массив не отсортирован), то сложность этой задачи O(n), а решение ее тривиально - перебор.

@Dennis Ritchie · 08.03.2015, 19:58 **[ТС]**

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

- не понял...

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

найти индексы элементов массива, совпадающих с заданным числом

А я теперь понял, почему вы подредактировали тему.

Нет. Задача состоит в том, чтобы проверить массив на наличие ~~одинакового элемента (числа или строки)~~ элементов, совпадающих с заданным значением. Вам знакома функция count() в C++?

@Catstail · 08.03.2015, 20:05

Сообщение от Dennis Ritchie

А я теперь понял, почему вы подредактировали тему.

- и опять подредактирую - "не одинакового элемента", а элементов, совпадающих с заданным значением. Писать "одинакового элемента" неграмотно.

@Ev_Hyper · 08.03.2015, 20:06

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

Если задача формулируется так: найти индексы элементов массива, совпадающих с заданным числом (и массив не отсортирован), то сложность этой задачи O(n), а решение ее тривиально - перебор.

Catstail, Имеется ввиду экономия времени на написание программы - по максимуму использовать стандартные функции. Для спортивных программистов это очень важно.

@Catstail · 08.03.2015, 20:10

Сообщение от Dennis Ritchie

Вам знакома функция count() в C++

- именно это она и делает.

Добавлено через 3 минуты

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

Имеется ввиду экономия времени на написание программы - по максимуму использовать стандартные функции. Для спортивных программистов это очень важно.

- Бога ради... Если целевая функция - реализовать как можно быстрее, то наверное.

@Dennis Ritchie · 08.03.2015, 20:23 **[ТС]**

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

- и опять подредактирую

Наконец-то, нашёлся на этом форуме человек, который знает русский язык лучше, чем я.

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

а самому открыть

Ev_Hyper, и так часто открываю. Просто испытываю 50%-ую трудность чтения по-английски. Когда английский подтяну, тогда будет проще.

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

Вы же D - программист, а не я:

Поэтому только что я и придумал способ, который проще записать, чем ваш

:

C++
1
2
3
4
5
6
7
8
9
import std.stdio;
import std.algorithm;
 
void main() {
 
    auto a = [3, 5, 8];
 
    writeln(find(remove(a, 1), 5).length != 0);     // prints false
}

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

по максимуму использовать стандартные функции. Для спортивных программистов это очень важно.

Важно, но не очень и не для всех.

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

- именно это она и делает.

Не совсем. Она возвращает количество элементов, совпадающих с заданным значением. Но мне в отличие от функции count() не нужно проверять количество, совпадающих элементов. Мне нужно проверить массив на наличие хотя бы одного элемента, совпадающего по значению с данным, и вернуть true (а лучше первый индекс совпадающего элемента, хотя возникнет проблема с возвратом нулевого индекса, ведь он занят под false) или false. Да, вот так всё у меня сложно.

@Ev_Hyper · 08.03.2015, 20:32

Сообщение от Dennis Ritchie

Поэтому только что я и придумал способ, который проще записать, чем ваш

Dennis Ritchie, такое поведение нормально?

Java
1
2
3
4
5
6
7
8
9
10
import std.stdio;
import std.algorithm;
 
void main() {
 
    auto a = [3, 5, 8];
 
    writeln(find(remove(a, 1), 5).length != 0);     // prints false
    writeln(a);
}

Code
1
2
false
[3, 8, 8] //???

http://ideone.com/grupRJ

@Catstail · 08.03.2015, 20:33

Сообщение от Dennis Ritchie

Но мне в отличие от функции count() не нужно проверять количество, совпадающих элементов. Мне нужно проверить массив на наличие хотя бы одного элемента, совпадающего по значению с данным, и вернуть true (а лучше первый индекс совпадающего элемента, хотя возникнет проблема с возвратом нулевого индекса, ведь он занят под false) или false. Да, вот так всё у меня сложно.

- господи! Вся проблема решается вот таким "сложным" кодом:

C
1
2
3
4
5
6
int isIn(int v, int *arr, int n)
{
   int i;
   for (i=0; i<n; i++) if (arr[i]==v) return i;
   return -1;
}

"Мы верим твердо
в героев спорта!
Нам победа как воздух нужна!
Мы хотим всем рекордам
наши звонкие дать имена!" - песня советских лет...

@Dennis Ritchie · 08.03.2015, 20:41 **[ТС]**

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

Вся проблема решается вот таким "сложным" кодом:

Нет. Не решается. Вы забыли про один нюанс. А что, если совпадающий элемент - это строка? Ваша функция не сработает.
То ли дело стандартная find() (универсальная). Вам же придётся писать гомогенную функцию с темплейтами, чтобы она стала универсальной.

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

песня советских лет...

Да, спортивное программирование не зря так названо. Уж поверьте.

@Catstail · 08.03.2015, 20:47

Сообщение от Dennis Ritchie

А что, если совпадающий элемент - это строка?

- а с какого перепуга строка окажется в int-массиве? И опять "совпадающий элемент"... Не "совпадающий", а "искомый". Если язык позволяет хранить в одном массиве и числа и строки, все достаточно просто. Алгоритм тот же.

Сообщение от Dennis Ritchie

Да, спортивное программирование не зря так названо.

- а в чем его суть в таком случае? Помнить как можно больше стандартных функций?

@Dennis Ritchie · 08.03.2015, 21:01 **[ТС]**

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

- а в чем его суть в таком случае? Помнить как можно больше стандартных функций?

Главная суть - знание алгоритмов и эффективное их применение.

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

- а с какого перепуга строка окажется в int-массиве?

Потребности со временем меняются. Вот и у меня появилась потребность проверять не только int-, но и string-массивы.
В D наконец-то избавились от такого ненужного понятия, как map:

C++
1
string[string] array;

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

И опять "совпадающий элемент"...

Когда писал, то знал, что вы опять докопаетесь до этого слова (мне просто лень было подобрать нужное)...

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

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

Такого ещё не придумали, насколько я знаю, но всё же универсальные функции лучше. В индексах позволяет:

C++
1
int[string][int] array;

@Catstail · 08.03.2015, 21:33

Сообщение от Dennis Ritchie

Главная суть - знание алгоритмов и эффективное их применение.

- не ощущаю этого по дискуссии. Алгоритм решения этой задачи ничтожен и не стОит серьезного обсуждения.

Сообщение от Dennis Ritchie

вы опять докопаетесь до этого слова (мне просто лень было подобрать нужное)

- мои обязанности состоят в том, чтобы следить за порядком в разделе (а порядок включает грамотность). "Лень подбирать" - рассматриваю, как хамство.

Сообщение от Dennis Ritchie

Такого ещё не придумали,

- такое уже давно придумали... В PHP, к примеру или в VB/VBA или в JavaScript-е. В VB есть контейнерный тип данных Variant, который может хранить что угодно. Поэтому в VB/VBA задача имеет очевидное решение:

Visual Basic
1
2
3
4
5
6
7
8
9
Function Find(A() as variant, v as Variant) As Variant
  for i%=1 to Ubound(A,1)
      if A(i%)=v then 
         Find=i%
         Exit function
      end if
  Next i%
  Find=False
End Function

Эта функция может вернуть индекс первого вхождения, а может логическое False (нет совпадений).

Добавлено через 7 минут
А вот как это же выглядит в Лиспе:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(defun find (arr el &optional (p 0))
  (cond ((null arr) nil)
        ((equal el (car arr)) p)
        (t (find (cdr arr) el (+ p 1)))))
 
==> find
 
(find '(1 4.5 "проба" a t 3/4) 4.5)
 
==> 1 ;; элемент стоит в поз. 1 (нумерация с нуля)
 
(find '(1 4.5 "проба" a t 3/4) 77)
 
==> NIL ;; элемент не найден
 
(find '(1 4.5 "проба" a t 3/4) "проба")
 
==> 2 ;; стоит в поз. 2
 
(find '(1 4.5 "проба" a t 3/4) 3/4)
 
==> 5 ;; стоит в поз. 5

@Dennis Ritchie · 08.03.2015, 22:25 **[ТС]**

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

"Лень подбирать" - рассматриваю, как хамство.

Если вы считаете это хамством, то вы не современны. Может быть, и эту фразу будете рассматривать, как хамство?

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

а порядок включает грамотность

Грамотность включает в себя совмещение правил русского языка и интернет-сленга, касается даже учителей русского языка. Если не умеете перейти на интернет-сленг, там где это уместно, то вы не грамотны (слова известного русского языковеда). Слово "совпадающий" никак не изменило смысл мною сказанного, и вы без труда поняли меня. В чём неграмотность? Ну, конечно, это хорошо, что вы следите за грамотностью. По-моему, кроме вас, за грамотностью русского языка не следит не один из модераторов (поэтому с неграмотностью в интернете бесполезно бороться). Теперь я, зная о том, что вы следите за грамотностью в этом разделе, буду стараться писать грамотно (и это я писал без всякого хамства).

Не по теме:

P.S. Когда я учился в школе, я был олимпиадником по русскому языку (и не только), выиграл областную олимпиаду и на этом остановился. Мне часто казалось, что люди в интернете очень не грамотны. А потом, в один прекрасный момент, я понял, что бороться с неграмотностью в интернете - это бред.

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

В VB есть контейнерный тип данных Variant

В D тоже есть (я имел в виду поддержку таких массивов на уровне самого ЯП, что-то вроде string-int[] array):

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
import std.stdio;
import std.variant;
 
alias IntOrStr = Algebraic!(int, string);
 
IntOrStr[] makeIntOrStrArray(T...)(T vals)
{
    import std.algorithm;
    import std.array;
    
    auto result = new IntOrStr[](T.length);
    foreach (i, val; vals)
    {
        result[i] = IntOrStr(val);
    }
    
    return result;
}
 
void main()
{
    IntOrStr[] arr = makeIntOrStrArray(4, "five", 5, "f", "k", 6, "example", 7);
 
    writeln(arr);   // prints [4, "five", 5, "f", "k", 6, "example", 7]
}

P.S. Спасибо, я раньше не знал для чего нужен этот заголовочный файл std.variant, хотя вас успели опередить на официальном форуме D. Просто я ещё не владею темплейтами и гомогенными функциями, чтобы это самому написать.

@Catstail · 08.03.2015, 22:51

Сообщение от Dennis Ritchie

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

- вы лучше не спорьте... Сленг - это специфический набор слов. А у вас - элементарное неумение выражать свои мысли. Ваше неумение можно назвать воинствующим (не хочу - лень). Да, это форма хамства.

Сообщение от Dennis Ritchie

Когда я учился в школе, я был олимпиадником по русскому языку (и не только)

- не верю! Человек, любящий и знающий русский язык, знает смысл слов и употребляет их к месту. Вижу, я вас задел... А вы не нарывайтесь, просто пишите грамотно. И ни у кого не будет претензий. Могу дать добрый совет старшего: аргументы должны легко подтверждаться. Ну как я проверю, что вы в школе были олимпиадником по русскому языку? Такие аргументы обычно высказывают подростки. "Учитесь властвовать собой" - это знаете, откуда?

Сообщение от Dennis Ritchie

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

- не скажите... На респектабельных сайтах вы безграмотности не найдете. Вот я и хочу, чтобы киберфорум был респектабельным.

@Dennis Ritchie · 08.03.2015, 23:30 **[ТС]**

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

Да, это форма хамства.

ОК.

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

Человек, любящий и знающий русский язык

Кто вам сказал, что я его люблю?

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

Вижу, я вас задел...

Нет. Меня смогли задеть только в разделе "Священные войны".

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

"Учитесь властвовать собой" - это знаете, откуда?

Нет. Не люблю читать художественную литературу (даже презираю так же, как и отечественный кинематограф), поэтому пришлось глянуть в интернете.

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

- не верю!

Этим задели. Доказательства последуют через несколько дней...
Ещё задели неприязнью к хакерам в одной теме на форуме (слышали про "золотого" хакера из России? Я считаю, что он гений). Больше ничем вы меня не задели.

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

Вот я и хочу, чтобы киберфорум был респектабельным.

Тогда надо, чтобы все модераторы киберфорума следили за грамотностью.

@Catstail · 08.03.2015, 23:45

Не по теме:

Сообщение от Dennis Ritchie

Доказательства последуют через несколько дней

- не трудитесь... Это доказать невозможно. Ну покажете вы скан чего-нибудь. Что подтвердит, что он ваш? Да и странно. Олимпиадник по русскому языку русский язык не любит, слова подбирать ленится. Хорош олимпиадник!..

Сообщение от Dennis Ritchie

Не люблю читать художественную литературу (даже презираю так же, как и отечественный кинематограф), поэтому пришлось глянуть в интернете.

- приятно иметь дело с такими
культурными людьми.

Сообщение от Dennis Ritchie

Ещё задели неприязнью к хакерам в одной теме на форуме (слышали про "золотого" хакера из России? Я считаю, что он гений).

- и что? Многие преступники являются весьма умными людьми. Вот слово "гений" я бы употреблять в данном контексте поостерегся. Т.к. полностью согласен с одним известным автором, который сказал "Гений и злодейство - две вещи несовместные" (посмотрите в Сети).

Впрочем, дискуссия отошла слишком далеко от языка D.

@Ev_Hyper · 08.03.2015, 23:50

Dennis Ritchie, а мой вопрос из поста:
https://www.cyberforum.ru/post7315631.html
вы почему проигнорировали?

@Catstail · 08.03.2015, 23:53

Не по теме:

Ev_Hyper, это я виноват

@Dennis Ritchie · 09.03.2015, 00:18 **[ТС]**

Сообщение от Ev_Hyper"

такое поведение нормально?

Не знаю. Спрошу на официальном форуме. Может быть, и нормальное. А, может быть, и нет. Ведь D до сих пор находится в активной разработке.

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

Ну покажете вы скан чего-нибудь.

Хорошо. Фото сотни грамот показывать вам бесполезно. Скажете, что у меня цветной принтер, и что я сам всё это быстро напечатал.
А это тоже не моё, или я на 3D-принтере напечатал, который купил за 300 тысяч рублей, или скажете, что я быстро у кого-то одолжил?

Новые блоги и статьи Все статьи Все блоги /
Альцгеймер и колоссальный объем вычислений Programma_Boinc 08.08.2026 Альцгеймер и колоссальный объем вычислений Сейчас по направлению болезни Альцгеймера идет колоссальный объем вычислений. Это один из главных приоритетов проекта. Такой массовый наплыв задач. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .

@Ev_Hyper Заблокирован
	08.03.2015, 23:50
	Dennis Ritchie, а мой вопрос из поста: https://www.cyberforum.ru/post7315631.html вы почему проигнорировали? 0

@Catstail
	08.03.2015, 23:53
	Не по теме: Ev_Hyper, это я виноват 0