Π Π°Π±ΠΎΡ‚Π° с коллСкциями Π΄Π°Π½Π½Ρ‹Ρ… являСтся ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· самых частых Π·Π°Π΄Π°Ρ‡ ΠΏΡ€ΠΈ написании ΠΊΠΎΠ΄Π° Π½Π° языкС ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ 1Π‘:ΠŸΡ€Π΅Π΄ΠΏΡ€ΠΈΡΡ‚ΠΈΠ΅. Π Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ постоянно ΡΡ‚Π°Π»ΠΊΠΈΠ²Π°ΡŽΡ‚ΡΡ с Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎΡΡ‚ΡŒΡŽ ΡΠΎΠΏΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ Π΄Π²Π° Π½Π°Π±ΠΎΡ€Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, Π½Π°ΠΉΡ‚ΠΈ отличия ΠΈΠ»ΠΈ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ Π΄ΡƒΠ±Π»ΠΈΠΊΠ°Ρ‚ΠΎΠ². ПониманиС Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½ΠΎ ΡΡ€Π°Π²Π½ΠΈΡ‚ΡŒ 2 массива 1Π‘, критичСски Π²Π°ΠΆΠ½ΠΎ для написания ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ ΠΈ Π½Π°Π΄Π΅ΠΆΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°, особСнно ΠΏΡ€ΠΈ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ Π±ΠΎΠ»ΡŒΡˆΠΈΡ… объСмов ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ.

БущСствуСт мноТСство ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ΠΎΠ² ΠΊ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡŽ этой Π·Π°Π΄Π°Ρ‡ΠΈ: ΠΎΡ‚ использования встроСнных ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ² сравнСния Π΄ΠΎ написания слоТных Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Ρ… Ρ†ΠΈΠΊΠ»ΠΎΠ². Π’Ρ‹Π±ΠΎΡ€ ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠ³ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° зависит ΠΎΡ‚ Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎ ΠΈΠΌΠ΅Π½Π½ΠΎ Π²Ρ‹ Ρ…ΠΎΡ‚ΠΈΡ‚Π΅ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅: логичСскоС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ истинности, список Π½ΠΎΠ²Ρ‹Ρ… элСмСнтов ΠΈΠ»ΠΈ ΠΈΠ½Π΄Π΅ΠΊΡΠ°Ρ†ΠΈΡŽ расхоТдСний. Π’ этой ΡΡ‚Π°Ρ‚ΡŒΠ΅ ΠΌΡ‹ рассмотрим основныС стратСгии ΠΈ Π½ΡŽΠ°Π½ΡΡ‹ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ.

Ошибки ΠΏΡ€ΠΈ сравнСнии часто Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‚ ΠΈΠ·-Π·Π° нСпонимания Ρ‚ΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ с ссылочными Ρ‚ΠΈΠΏΠ°ΠΌΠΈ Π΄Π°Π½Π½Ρ‹Ρ…. ΠŸΡ€ΠΎΡΡ‚ΠΎΠ΅ использованиС Π·Π½Π°ΠΊΠ° равСнства ΠΌΠΎΠΆΠ΅Ρ‚ Π΄Π°Ρ‚ΡŒ Π½Π΅ΠΎΠΆΠΈΠ΄Π°Π½Π½Ρ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚, Ссли ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹ Π²Π½ΡƒΡ‚Ρ€ΠΈ массивов Π±Ρ‹Π»ΠΈ созданы Π² Ρ€Π°Π·Π½Ρ‹Ρ… участках памяти, Π΄Π°ΠΆΠ΅ Ссли ΠΈΡ… содСрТимоС ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ‡Π½ΠΎ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Π²Π°ΠΆΠ½ΠΎ Ρ€Π°Π·ΠΎΠ±Ρ€Π°Ρ‚ΡŒΡΡ Π² ΠΌΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌΠ°Ρ… Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π΄Π²ΠΈΠΆΠΊΠ° 1Π‘ Π³Π»ΡƒΠ±ΠΆΠ΅.

Π‘Π°Π·ΠΎΠ²ΠΎΠ΅ сравнСниС ссылок ΠΈ содСрТимого

Π‘Π°ΠΌΡ‹ΠΉ ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½Ρ‹ΠΉ способ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ‡Π½ΠΎΡΡ‚ΡŒ Π΄Π²ΡƒΡ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… β€” ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ =. Однако Π² контСкстС массивов это Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ спСцифичСски. Если Π²Ρ‹ присвоили ΠΎΠ΄Π½Ρƒ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½ΡƒΡŽ Π΄Ρ€ΡƒΠ³ΠΎΠΉ, ΠΎΠ½ΠΈ Π±ΡƒΠ΄ΡƒΡ‚ ΡƒΠΊΠ°Π·Ρ‹Π²Π°Ρ‚ΡŒ Π½Π° ΠΎΠ΄ΠΈΠ½ ΠΈ Ρ‚ΠΎΡ‚ ΠΆΠ΅ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ Π² памяти, ΠΈ сравнСниС Π²Π΅Ρ€Π½Π΅Ρ‚ Π˜ΡΡ‚ΠΈΠ½Π°. Но Ссли Π²Ρ‹ создали Π΄Π²Π° Ρ€Π°Π·Π½Ρ‹Ρ… массива с ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²Ρ‹ΠΌ Π½Π°Π±ΠΎΡ€ΠΎΠΌ элСмСнтов, прямоС сравнСниС Π²Π΅Ρ€Π½Π΅Ρ‚ Π›ΠΎΠΆΡŒ.

Π­Ρ‚ΠΎ происходит ΠΏΠΎΡ‚ΠΎΠΌΡƒ, Ρ‡Ρ‚ΠΎ массив являСтся ссылочным Ρ‚ΠΈΠΏΠΎΠΌ. ΠŸΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° сравниваСт Π½Π΅ содСрТимоС ячССк, Π° адрСса ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Π² ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ памяти. Для Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠ° это ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ для ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ фактичСского равСнства Π΄Π°Π½Π½Ρ‹Ρ… Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹. Π˜Π³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ этого Ρ„Π°ΠΊΡ‚Π° ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ логичСским ошибкам Π² Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°Ρ… синхронизации Π΄Π°Π½Π½Ρ‹Ρ….

Рассмотрим ΠΏΡ€ΠΎΡΡ‚ΡƒΡŽ ΡΠΈΡ‚ΡƒΠ°Ρ†ΠΈΡŽ, ΠΊΠΎΠ³Π΄Π° Π½ΡƒΠΆΠ½ΠΎ ΡƒΠ±Π΅Π΄ΠΈΡ‚ΡŒΡΡ, Ρ‡Ρ‚ΠΎ массивы ΡΡΡ‹Π»Π°ΡŽΡ‚ΡΡ Π½Π° ΠΎΠ΄ΠΈΠ½ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚. Π­Ρ‚ΠΎ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ ΠΏΠΎΠ»Π΅Π·Π½ΠΎ для ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ лишнСго копирования Π΄Π°Π½Π½Ρ‹Ρ…. Если ссылка одинаковая, дальнСйшая глубокая ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ° Π½Π΅ трСбуСтся, Ρ‡Ρ‚ΠΎ экономит рСсурсы процСссора.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: Никогда Π½Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ равСнства для ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ идСнтичности содСрТимого Π΄Π²ΡƒΡ… нСзависимо созданных массивов. Π­Ρ‚ΠΎ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎ Π²Π΅Ρ€Π½Π΅Ρ‚ Π»ΠΎΠΆΠ½Ρ‹ΠΉ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚, Π΄Π°ΠΆΠ΅ Ссли Π²ΠΈΠ·ΡƒΠ°Π»ΡŒΠ½ΠΎ Π΄Π°Π½Π½Ρ‹Π΅ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡŽΡ‚.

Для ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ содСрТимого Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠ΅Ρ€Π΅Π±ΠΈΡ€Π°Ρ‚ΡŒ элСмСнты. БущСствуСт стандартный ΠΏΠΎΠ΄Ρ…ΠΎΠ΄, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π·Π°ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ Π² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠΌ сравнСнии элСмСнтов ΠΏΠΎ индСксам. Если Π΄Π»ΠΈΠ½Ρ‹ массивов Ρ€Π°Π·Π»ΠΈΡ‡Π°ΡŽΡ‚ΡΡ, ΠΎΠ½ΠΈ автоматичСски ΡΡ‡ΠΈΡ‚Π°ΡŽΡ‚ΡΡ Π½Π΅Ρ€Π°Π²Π½Ρ‹ΠΌΠΈ. Если Π΄Π»ΠΈΠ½Ρ‹ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡŽΡ‚, Ρ†ΠΈΠΊΠ» ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ ΠΏΠΎ всСм индСксам ΠΈ сравниваСт значСния.

πŸ’‘

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ свойство "ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ" массива ΠΏΠ΅Ρ€Π΅Π΄ Ρ†ΠΈΠΊΠ»ΠΎΠΌ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ лишнСй ΠΈΡ‚Π΅Ρ€Π°Ρ†ΠΈΠΈ, Ссли Ρ€Π°Π·ΠΌΠ΅Ρ€Ρ‹ ΠΊΠΎΠ»Π»Π΅ΠΊΡ†ΠΈΠΉ ΠΈΠ·Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎ Ρ€Π°Π·Π½Ρ‹Π΅.

Поиск Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΉ ΠΌΠ΅ΠΆΠ΄Ρƒ двумя коллСкциями

Часто Π·Π°Π΄Π°Ρ‡Π° стоит Π½Π΅ Π² ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ΅ ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ равСнства, Π° Π² выявлСнии ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½Ρ‹Ρ… ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠΉ. НапримСр, Π²Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ элСмСнты, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΡ€ΠΈΡΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‚ Π² ΠΏΠ΅Ρ€Π²ΠΎΠΌ массивС, Π½ΠΎ ΠΎΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΡƒΡŽΡ‚ Π²ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ. Π­Ρ‚ΠΎ типичная Π·Π°Π΄Π°Ρ‡Π° ΠΏΡ€ΠΈ Ρ„ΠΎΡ€ΠΌΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠΈ ΠΎΡ‚Ρ‡Π΅Ρ‚ΠΎΠ² ΠΎΠ± ΠΈΠ·ΠΌΠ΅Π½Π΅Π½ΠΈΠΈ состава Π½ΠΎΠΌΠ΅Π½ΠΊΠ»Π°Ρ‚ΡƒΡ€Ρ‹ ΠΈΠ»ΠΈ ΠΎΠ±Π½ΠΎΠ²Π»Π΅Π½ΠΈΠΈ списков ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»Π΅ΠΉ.

Для Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Ρ‚Π°ΠΊΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ» ΠΈΠ»ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄ Найти. Π’Π½Π΅ΡˆΠ½ΠΈΠΉ Ρ†ΠΈΠΊΠ» ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ ΠΏΠΎ элСмСнтам ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ массива, Π° Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΉ пытаСтся Π½Π°ΠΉΡ‚ΠΈ совпадСниС Π²ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ. Если совпадСниС Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½ΠΎ, элСмСнт добавляСтся Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚ΠΈΡ€ΡƒΡŽΡ‰ΠΈΠΉ список Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΉ. Π’Π°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ аккуратности с ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒΡŽ.

Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π»ΠΈΠ½Π΅ΠΉΠ½ΠΎ-квадратичная, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ O(N*M). Π­Ρ‚ΠΎ Π·Π½Π°Ρ‡ΠΈΡ‚, Ρ‡Ρ‚ΠΎ ΠΏΡ€ΠΈ ΡƒΠ²Π΅Π»ΠΈΡ‡Π΅Π½ΠΈΠΈ количСства элСмСнтов врСмя выполнСния растСт ΡΠΊΡΠΏΠΎΠ½Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎ. Для Π½Π΅Π±ΠΎΠ»ΡŒΡˆΠΈΡ… массивов (Π΄ΠΎ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… сотСн элСмСнтов) это Π½Π΅ ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎ, Π½ΠΎ для тысяч записСй Ρ‚Π°ΠΊΠΎΠΉ ΠΊΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ‚ "ΠΏΠΎΠ΄Π²Π΅ΡΠΈΡ‚ΡŒ" систСму.

  • πŸ” Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄ Найти() для ускорСния поиска Π²Π½ΡƒΡ‚Ρ€ΠΈ Π²Ρ‚ΠΎΡ€ΠΎΠ³ΠΎ массива вмСсто Ρ€ΡƒΡ‡Π½ΠΎΠ³ΠΎ Ρ†ΠΈΠΊΠ»Π°.
  • πŸš€ Для Π±ΠΎΠ»ΡŒΡˆΠΈΡ… объСмов Π΄Π°Π½Π½Ρ‹Ρ… рассмотритС использованиС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ² Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΈ ΠΈΡ… ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² сравнСния.
  • πŸ“‰ ΠžΠΏΡ‚ΠΈΠΌΠΈΠ·ΠΈΡ€ΡƒΠΉΡ‚Π΅ ΠΊΠΎΠ΄, прСрывая Ρ†ΠΈΠΊΠ» сразу послС нахоТдСния ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ совпадСния с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€Π° ΠŸΡ€Π΅Ρ€Π²Π°Ρ‚ΡŒ.

Π’Π°ΠΆΠ½ΠΎ ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ Ρ‚ΠΈΠΏ Π΄Π°Π½Π½Ρ‹Ρ… Π²Π½ΡƒΡ‚Ρ€ΠΈ массива. Если Π²Ρ‹ сравниваСтС строки, рСгистр символов ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. Π’ 1Π‘ сравнСниС строк Ρ‡ΡƒΠ²ΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΊ рСгистру ΠΏΠΎ ΡƒΠΌΠΎΠ»Ρ‡Π°Π½ΠΈΡŽ Π² Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… контСкстах, Π½ΠΎ ΠΏΡ€ΠΈ использовании стандартных ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΎΡ€ΠΎΠ² ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ учитываСтся настройка Π»ΠΎΠΊΠ°Π»ΠΈ. Для чисСл ΠΈ Π΄Π°Ρ‚ сравнСниС происходит строго ΠΏΠΎ Π·Π½Π°Ρ‡Π΅Π½ΠΈΡŽ.

πŸ“Š Какой ΠΌΠ΅Ρ‚ΠΎΠ΄ сравнСния Π²Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚Π΅ Ρ‡Π°Ρ‰Π΅ всСго?
Π ΡƒΡ‡Π½ΠΎΠΉ Ρ†ΠΈΠΊΠ»
ΠœΠ΅Ρ‚ΠΎΠ΄ Найти
Π’Π°Π±Π»ΠΈΡ†Ρ‹ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ
ВстроСнныС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ

ΠžΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΏΡ€ΠΈ Ρ€Π°Π±ΠΎΡ‚Π΅ с большими Π΄Π°Π½Π½Ρ‹ΠΌΠΈ

Когда объСм Π΄Π°Π½Π½Ρ‹Ρ… ΠΏΡ€Π΅Π²Ρ‹ΡˆΠ°Π΅Ρ‚ нСсколько тысяч записСй, стандартныС Ρ†ΠΈΠΊΠ»Ρ‹ становятся ΡƒΠ·ΠΊΠΈΠΌ мСстом. Π’ Ρ‚Π°ΠΊΠΈΡ… случаях ΠΎΠΏΡ‹Ρ‚Π½Ρ‹Π΅ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΈ 1Π‘ пСрСходят ΠΎΡ‚ Ρ€Π°Π±ΠΎΡ‚Ρ‹ с массивами ΠΊ использованию Π±ΠΎΠ»Π΅Π΅ ΠΌΠΎΡ‰Π½Ρ‹Ρ… структур Π΄Π°Π½Π½Ρ‹Ρ…. ΠžΡΠ½ΠΎΠ²Π½Ρ‹ΠΌ инструмСнтом ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ здСсь выступаСт ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ Π’Π°Π±Π»ΠΈΡ†Π°Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ.

Π’Π°Π±Π»ΠΈΡ†Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ позволяСт Π·Π°Π³Ρ€ΡƒΠΆΠ°Ρ‚ΡŒ Π΄Π°Π½Π½Ρ‹Π΅ ΠΈΠ· массивов ΠΈ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ встроСнныС, высокооптимизированныС ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Π½Π°Π±ΠΎΡ€Π°ΠΌΠΈ записСй. НапримСр, ΠΌΠΎΠΆΠ½ΠΎ быстро Π½Π°ΠΉΡ‚ΠΈ отличия, ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΈΠ»ΠΈ спСциализированныС ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ. Π­Ρ‚ΠΎ ΠΏΠ΅Ρ€Π΅ΠΊΠ»Π°Π΄Ρ‹Π²Π°Π΅Ρ‚ Π·Π°Π΄Π°Ρ‡Ρƒ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ с вашСго ΠΊΠΎΠ΄Π° Π½Π° ядро ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹.

Π•Ρ‰Π΅ ΠΎΠ΄ΠΈΠ½ ΠΏΡ€ΠΈΠ΅ΠΌ β€” ΠΏΡ€Π΅Π΄Π²Π°Ρ€ΠΈΡ‚Π΅Π»ΡŒΠ½Π°Ρ сортировка массивов. Если ΠΎΠ±Π° массива отсортированы ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ ΠΊΠ»ΡŽΡ‡Ρƒ, сравнСниС ΠΌΠΎΠΆΠ½ΠΎ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Π·Π° ΠΎΠ΄ΠΈΠ½ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ (линСйная ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ O(N)). Π­Ρ‚ΠΎ ΠΊΠ°Ρ€Π΄ΠΈΠ½Π°Π»ΡŒΠ½ΠΎ быстрСС, Ρ‡Π΅ΠΌ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ Ρ†ΠΈΠΊΠ»Ρ‹. Однако сама сортировка Ρ‚ΠΎΠΆΠ΅ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ, поэтому этот ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠΎΠΏΡ€Π°Π²Π΄Π°Π½ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΏΡ€ΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡ€Π°Ρ‚Π½ΠΎΠΌ сравнСнии ΠΎΠ΄Π½ΠΈΡ… ΠΈ Ρ‚Π΅Ρ… ΠΆΠ΅ Π΄Π°Π½Π½Ρ‹Ρ….

ΠœΠ΅Ρ‚ΠΎΠ΄ Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π Π΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡƒΠ΅ΠΌΡ‹ΠΉ объСм Π΄Π°Π½Π½Ρ‹Ρ… Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ
ΠŸΡ€ΡΠΌΠΎΠ΅ сравнСниС ссылок O(1) Π›ΡŽΠ±ΠΎΠΉ Минимальная
Π’Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ Ρ†ΠΈΠΊΠ»Ρ‹ O(N^2) Π”ΠΎ 500 элСмСнтов Низкая
ΠœΠ΅Ρ‚ΠΎΠ΄ Найти O(N*M) Π”ΠΎ 2000 элСмСнтов БрСдняя
Π’Π°Π±Π»ΠΈΡ†Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ O(N log N) Π‘ΠΎΠ»Π΅Π΅ 5000 элСмСнтов Высокая

НС стоит Π·Π°Π±Ρ‹Π²Π°Ρ‚ΡŒ ΠΎ ΠΏΠΎΡ‚Ρ€Π΅Π±Π»Π΅Π½ΠΈΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ памяти. Π‘ΠΎΠ·Π΄Π°Π½ΠΈΠ΅ ΠΏΡ€ΠΎΠΌΠ΅ΠΆΡƒΡ‚ΠΎΡ‡Π½Ρ‹Ρ… структур для сравнСния ΠΌΠΎΠΆΠ΅Ρ‚ привСсти ΠΊ росту потрСблСния памяти сСрвСром 1Π‘. Π’ высоконагруТСнных систСмах это ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹Π·Π²Π°Ρ‚ΡŒ Π²Ρ‹Π³Ρ€ΡƒΠ·ΠΊΡƒ сСансов ΠΈΠ»ΠΈ Π·Π°ΠΌΠ΅Π΄Π»Π΅Π½ΠΈΠ΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π΄Ρ€ΡƒΠ³ΠΈΡ… ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»Π΅ΠΉ.

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: ΠŸΡ€ΠΈ ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ массивов с Π±ΠΎΠ»Π΅Π΅ Ρ‡Π΅ΠΌ 10 000 элСмСнтов Π² Ρ†ΠΈΠΊΠ»Π΅ ΠΎΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ тСстируйтС ΠΊΠΎΠ΄ Π½Π° ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ. Π’ΠΎ, Ρ‡Ρ‚ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ быстро Π½Π° тСстовой Π±Π°Π·Π΅ с 10 записями, ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ ΠΌΠΈΠ½ΡƒΡ‚Ρ‹ Π½Π° Ρ€Π΅Π°Π»ΡŒΠ½ΠΎΠΉ Π±Π°Π·Π΅.

Π‘Π΅ΠΊΡ€Π΅Ρ‚ быстрой Ρ€Π°Π±ΠΎΡ‚Ρ‹ с большими массивами

Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΈΠ½Π΄Π΅ΠΊΡΠ°Ρ†ΠΈΡŽ. Если Π²Ρ‹ часто ΠΈΡ‰Π΅Ρ‚Π΅ элСмСнты ΠΏΠΎ ΠΊΠ°ΠΊΠΎΠΌΡƒ-Ρ‚ΠΎ ΠΊΠ»ΡŽΡ‡Ρƒ, создайтС Π²ΡΠΏΠΎΠΌΠΎΠ³Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΉ Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Ρƒ ΠΈΠ»ΠΈ Π’Π°Π±Π»ΠΈΡ†ΡƒΠ—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ с индСксом ΠΏΠΎ этому полю ΠΏΠ΅Ρ€Π΅Π΄ Π½Π°Ρ‡Π°Π»ΠΎΠΌ основного Ρ†ΠΈΠΊΠ»Π° сравнСния.

Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ массивов структур ΠΈ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ²

Битуация услоТняСтся, ΠΊΠΎΠ³Π΄Π° массивы содСрТат Π½Π΅ ΠΏΡ€ΠΈΠΌΠΈΡ‚ΠΈΠ²Π½Ρ‹Π΅ Ρ‚ΠΈΠΏΡ‹ (числа, строки), Π° слоТныС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹, Ρ‚Π°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€Π° ΠΈΠ»ΠΈ ссылки Π½Π° Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Ρ‹. Π’ этом случаС простоС сравнСниС Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ часто Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ Π±Π΅Π· Π΄ΠΎΠΏΠΎΠ»Π½ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠΉ Π»ΠΎΠ³ΠΈΠΊΠΈ. Π’Π°ΠΌ Π½ΡƒΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, ΠΏΠΎ ΠΊΠ°ΠΊΠΈΠΌ ΠΈΠΌΠ΅Π½Π½ΠΎ полям структуры Π±ΡƒΠ΄Π΅Ρ‚ ΠΏΡ€ΠΎΠΈΡΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ сравнСниС.

НапримСр, Ρƒ вас Π΅ΡΡ‚ΡŒ Π΄Π²Π° массива структур, ΠΎΠΏΠΈΡΡ‹Π²Π°ΡŽΡ‰ΠΈΡ… Ρ‚ΠΎΠ²Π°Ρ€Ρ‹. Π’ ΠΎΠ΄Π½ΠΎΠΉ структурС ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ лишнСС ΠΏΠΎΠ»Π΅ "ΠšΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΉ", ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π½Π΅ влияСт Π½Π° ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ Ρ‚ΠΎΠ²Π°Ρ€Π°. Если ΡΡ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ структуры Ρ†Π΅Π»ΠΈΠΊΠΎΠΌ ΠΊΠ°ΠΊ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹, ΠΎΠ½ΠΈ Π±ΡƒΠ΄ΡƒΡ‚ Ρ€Π°Π·Π½Ρ‹ΠΌΠΈ. НСобходимо ΠΈΠ·Π²Π»Π΅ΠΊΠ°Ρ‚ΡŒ ΠΊΠ»ΡŽΡ‡Π΅Π²Ρ‹Π΅ поля (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Артикул) ΠΈ ΡΡ€Π°Π²Π½ΠΈΠ²Π°Ρ‚ΡŒ ΠΈΠΌΠ΅Π½Π½ΠΎ ΠΈΡ….

Для этого ΡƒΠ΄ΠΎΠ±Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π²Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹ΠΉ массив ΠΊΠ»ΡŽΡ‡Π΅ΠΉ. Π’Ρ‹ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚Π΅ ΠΏΠΎ ΠΏΠ΅Ρ€Π²ΠΎΠΌΡƒ массиву, ΠΈΠ·Π²Π»Π΅ΠΊΠ°Π΅Ρ‚Π΅ Π½ΡƒΠΆΠ½ΠΎΠ΅ ΠΏΠΎΠ»Π΅ ΠΈ ΠΊΠ»Π°Π΄Π΅Ρ‚Π΅ Π΅Π³ΠΎ Π² Π½ΠΎΠ²Ρ‹ΠΉ массив простых Ρ‚ΠΈΠΏΠΎΠ². Π—Π°Ρ‚Π΅ΠΌ выполняСтС сравнСниС ΡƒΠΆΠ΅ этих ΡƒΠΏΡ€ΠΎΡ‰Π΅Π½Π½Ρ‹Ρ… массивов. Π­Ρ‚ΠΎ сниТаСт Π½Π°Π³Ρ€ΡƒΠ·ΠΊΡƒ Π½Π° систСму ΠΈ ΡƒΠΏΡ€ΠΎΡ‰Π°Π΅Ρ‚ Π»ΠΎΠ³ΠΈΠΊΡƒ ΠΊΠΎΠ΄Π°.


// ΠŸΡ€ΠΈΠΌΠ΅Ρ€ извлСчСния ΠΊΠ»ΡŽΡ‡Π΅ΠΉ для сравнСния

ΠœΠ°ΡΡΠΈΠ²ΠšΠ»ΡŽΡ‡Π΅ΠΉ1 = Новый Массив;

Для КаТдого Π­Π»Π΅ΠΌΠ΅Π½Ρ‚ Из ΠœΠ°ΡΡΠΈΠ²Π‘Ρ‚Ρ€ΡƒΠΊΡ‚ΡƒΡ€1 Π¦ΠΈΠΊΠ»

ΠœΠ°ΡΡΠΈΠ²ΠšΠ»ΡŽΡ‡Π΅ΠΉ1.Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ(Π­Π»Π΅ΠΌΠ΅Π½Ρ‚.Артикул);

ΠšΠΎΠ½Π΅Ρ†Π¦ΠΈΠΊΠ»Π°;

Π’Π°ΠΊΠΆΠ΅ стоит ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹ ΠΌΠΎΠ³ΡƒΡ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ Ρ€Π°Π·Π½Ρ‹Π΅ Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠ΅ прСдставлСния. Бсылка Π½Π° Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚, получСнная Ρ‡Π΅Ρ€Π΅Π· Π²Ρ‹Π±ΠΎΡ€ΠΊΡƒ, ΠΈ ссылка, созданная Ρ‡Π΅Ρ€Π΅Π· Π‘ΠΎΠ·Π΄Π°Ρ‚ΡŒΠ”ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Π‘ΡΡ‹Π»ΠΊΡƒ, ΠΌΠΎΠ³ΡƒΡ‚ вСсти сСбя ΠΏΠΎ-Ρ€Π°Π·Π½ΠΎΠΌΡƒ ΠΏΡ€ΠΈ сравнСнии, Ссли Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚ Π΅Ρ‰Π΅ Π½Π΅ записан. ВсСгда провСряйтС, ΡΠ²Π»ΡΡŽΡ‚ΡΡ Π»ΠΈ ссылки Π·Π°ΠΏΠΎΠ»Π½Π΅Π½Π½Ρ‹ΠΌΠΈ.

πŸ’‘

Π‘Ρ€Π°Π²Π½ΠΈΠ²Π°ΠΉΡ‚Π΅ слоТныС ΠΎΠ±ΡŠΠ΅ΠΊΡ‚Ρ‹ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΏΠΎ ΠΈΡ… ΡƒΠ½ΠΈΠΊΠ°Π»ΡŒΠ½Ρ‹ΠΌ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€Π°ΠΌ (ΠΊΠ»ΡŽΡ‡Π΅Π²Ρ‹ΠΌ полям), игнорируя слуТСбныС ΠΈΠ»ΠΈ измСняСмыС Π°Ρ‚Ρ€ΠΈΠ±ΡƒΡ‚Ρ‹, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΈΠ·Π±Π΅ΠΆΠ°Ρ‚ΡŒ Π»ΠΎΠΆΠ½Ρ‹Ρ… срабатываний.

ИспользованиС встроСнных Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΈ Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊ

ΠŸΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° 1Π‘ прСдоставляСт ряд встроСнных срСдств, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΌΠΎΠ³ΡƒΡ‚ ΡƒΠΏΡ€ΠΎΡΡ‚ΠΈΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡Ρƒ. Π₯отя прямого ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Π‘Ρ€Π°Π²Π½ΠΈΡ‚ΡŒΠœΠ°ΡΡΠΈΠ²Ρ‹ Π½Π΅Ρ‚, комбинация Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ БтрНайти (для строк), Массив.Найти ΠΈ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ Ρ€Π°Π±ΠΎΡ‚Ρ‹ с Ρ‚Π°Π±Π»ΠΈΡ†Π°ΠΌΠΈ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ позволяСт Ρ€Π΅ΡˆΠ°Ρ‚ΡŒ Π·Π°Π΄Π°Ρ‡Ρƒ элСгантно. Π’ соврСмСнных вСрсиях ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ ΠΏΠΎΡΠ²Π»ΡΡŽΡ‚ΡΡ Π½ΠΎΠ²Ρ‹Π΅ возмоТности, ΡƒΠΏΡ€ΠΎΡ‰Π°ΡŽΡ‰ΠΈΠ΅ Ρ€Π°Π±ΠΎΡ‚Ρƒ с коллСкциями.

Одним ΠΈΠ· ΠΌΠΎΡ‰Π½Ρ‹Ρ… инструмСнтов являСтся ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ БоотвСтствиС (Map). Π’Ρ‹ ΠΌΠΎΠΆΠ΅Ρ‚Π΅ Π·Π°Π³Ρ€ΡƒΠ·ΠΈΡ‚ΡŒ ΠΎΠ΄ΠΈΠ½ массив Π² соотвСтствиС, Π³Π΄Π΅ ΠΊΠ»ΡŽΡ‡ΠΎΠΌ Π±ΡƒΠ΄Π΅Ρ‚ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ элСмСнта, Π° Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ β€” индСкс ΠΈΠ»ΠΈ сам ΠΎΠ±ΡŠΠ΅ΠΊΡ‚. Поиск Π² соотвСтствии происходит ΠΌΠ³Π½ΠΎΠ²Π΅Π½Π½ΠΎ, Ρ‡Ρ‚ΠΎ Π΄Π΅Π»Π°Π΅Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ сравнСния ΠΎΡ‡Π΅Π½ΡŒ быстрым Π΄Π°ΠΆΠ΅ для Π±ΠΎΠ»ΡŒΡˆΠΈΡ… Π΄Π°Π½Π½Ρ‹Ρ….

Π‘ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊΠΈ стандартных подсистСм (Π‘Π‘ΠŸ) Ρ‚Π°ΠΊΠΆΠ΅ содСрТат Π³ΠΎΡ‚ΠΎΠ²Ρ‹Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ для Ρ€Π°Π±ΠΎΡ‚Ρ‹ с коллСкциями. Если Π²Ρ‹ Ρ€Π°Π·Ρ€Π°Π±Π°Ρ‚Ρ‹Π²Π°Π΅Ρ‚Π΅ Π² конфигурациях Π½Π° Π±Π°Π·Π΅ Π‘Π‘ΠŸ, ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡŒΡ‚Π΅ Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ ΠΌΠΎΠ΄ΡƒΠ»Π΅ΠΉ Π Π°Π±ΠΎΡ‚Π°Π‘ΠœΠ°ΡΡΠΈΠ²Π°ΠΌΠΈ ΠΈΠ»ΠΈ Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½Ρ‹Ρ…. ИспользованиС Π³ΠΎΡ‚ΠΎΠ²ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π° ΠΎΡ‚ Ρ„ΠΈΡ€ΠΌΡ‹ "1Π‘" ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΡƒΠ΅Ρ‚ Π»ΡƒΡ‡ΡˆΡƒΡŽ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΡŽ ΠΈ ΡƒΡ‡Π΅Ρ‚ всСх Π³Ρ€Π°Π½ΠΈΡ‡Π½Ρ‹Ρ… случаСв.

  • πŸ“š Π˜Π·ΡƒΡ‡ΠΈΡ‚Π΅ ΠΌΠΎΠ΄ΡƒΠ»ΡŒ Π Π°Π±ΠΎΡ‚Π°Π‘ΠœΠ°ΡΡΠΈΠ²Π°ΠΌΠΈ Π² Π‘Π‘ΠŸ ΠΏΠ΅Ρ€Π΅Π΄ написаниСм своСго вСлосипСда.
  • πŸ—ΊοΈ Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ БоотвСтствиС для ускорСния поиска элСмСнтов Π·Π° O(1).
  • βš™οΈ ΠŸΡ€ΠΈΠΌΠ΅Π½ΡΠΉΡ‚Π΅ Π’Π°Π±Π»ΠΈΡ†ΡƒΠ—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ для ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΉ, Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‰ΠΈΡ… сортировки ΠΈΠ»ΠΈ Π³Ρ€ΡƒΠΏΠΏΠΈΡ€ΠΎΠ²ΠΊΠΈ ΠΏΠ΅Ρ€Π΅Π΄ сравнСниСм.

ΠŸΠΎΠΌΠ½ΠΈΡ‚Π΅, Ρ‡Ρ‚ΠΎ встроСнныС Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ часто написаны Π½Π° Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½Π΅ΠΌ языкС ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ (C++), поэтому ΠΎΠ½ΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‚ΡΡ быстрСС, Ρ‡Π΅ΠΌ ΠΊΠΎΠ΄ Π½Π° встроСнном языкС 1Π‘, ΠΈΠ½Ρ‚Π΅Ρ€ΠΏΡ€Π΅Ρ‚ΠΈΡ€ΡƒΠ΅ΠΌΡ‹ΠΉ Π²ΠΈΡ€Ρ‚ΡƒΠ°Π»ΡŒΠ½ΠΎΠΉ машиной. ΠŸΡ€ΠΈΠΎΡ€ΠΈΡ‚Π΅Ρ‚ всСгда Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΎΡ‚Π΄Π°Π²Π°Ρ‚ΡŒΡΡ встроСнным ΠΌΠ΅Ρ‚ΠΎΠ΄Π°ΠΌ ΠΎΠ±ΡŠΠ΅ΠΊΡ‚ΠΎΠ².

⚠️ Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅: Π€ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π» стандартных подсистСм ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΡ‚Π»ΠΈΡ‡Π°Ρ‚ΡŒΡΡ Π² Ρ€Π°Π·Π½Ρ‹Ρ… вСрсиях Π±ΠΈΠ±Π»ΠΈΠΎΡ‚Π΅ΠΊ. ВсСгда ΡΠ²Π΅Ρ€ΡΠΉΡ‚Π΅ΡΡŒ с Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚Π°Ρ†ΠΈΠ΅ΠΉ вашСй ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎΠΉ вСрсии Π‘Π‘ΠŸ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΈΠΌΠ΅Π½Π° Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ ΠΈ ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Ρ‹ ΠΌΠΎΠ³ΡƒΡ‚ ΠΌΠ΅Π½ΡΡ‚ΡŒΡΡ.

β˜‘οΈ Π§Π΅ΠΊ-лист ΠΏΠ΅Ρ€Π΅Π΄ запуском сравнСния

Π’Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ: 0 / 4

ΠžΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ошибок ΠΈ Π³Ρ€Π°Π½ΠΈΡ‡Π½Ρ‹Π΅ случаи

ΠŸΡ€ΠΈ написании ΠΊΠΎΠ΄Π° сравнСния Π»Π΅Π³ΠΊΠΎ Π·Π°Π±Ρ‹Ρ‚ΡŒ ΠΎ ситуациях, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ выходят Π·Π° Ρ€Π°ΠΌΠΊΠΈ "идСального ΠΌΠΈΡ€Π°". Π§Ρ‚ΠΎ Π±ΡƒΠ΄Π΅Ρ‚, Ссли ΠΎΠ΄ΠΈΠ½ ΠΈΠ· массивов Ρ€Π°Π²Π΅Π½ НСопрСдСлСно? А Ссли массив пуст? Или Ссли Π² Π½Π΅ΠΌ Π΅ΡΡ‚ΡŒ элСмСнты Ρ‚ΠΈΠΏΠ° Null? Π’Π°ΠΊΠΈΠ΅ сцСнарии ΠΎΠ±ΡΠ·Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ Π½ΡƒΠΆΠ½ΠΎ ΠΏΡ€Π΅Π΄ΡƒΡΠΌΠ°Ρ‚Ρ€ΠΈΠ²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΏΡ€ΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π½Π΅ Π²Ρ‹Π΄Π°Π²Π°Π»ΠΎ критичСских ошибок ΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚Π΅Π»ΡŽ.

ΠŸΡƒΡΡ‚ΠΎΠΉ массив ΠΈ массив с ΠΎΠ΄Π½ΠΈΠΌ элСмСнтом Null β€” это Ρ€Π°Π·Π½Ρ‹Π΅ Π²Π΅Ρ‰ΠΈ. ΠŸΡƒΡΡ‚ΠΎΠΉ массив ΠΈΠΌΠ΅Π΅Ρ‚ количСство 0. Массив с Π½ΡƒΠ»Π΅ΠΌ ΠΈΠΌΠ΅Π΅Ρ‚ количСство 1. ΠŸΡ€ΠΈ сравнСнии это даст Ρ€Π°Π·Π½Ρ‹Π΅ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹. Π’Π°ΠΊΠΆΠ΅ стоит ΡƒΡ‡ΠΈΡ‚Ρ‹Π²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΠ° ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΊ свойству Π½Π΅ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅Π³ΠΎ элСмСнта Π²Ρ‹Π·ΠΎΠ²Π΅Ρ‚ ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅.

РСкомСндуСтся всСгда ΠΎΠ±ΠΎΡ€Π°Ρ‡ΠΈΠ²Π°Ρ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ сравнСния Π² ΠΊΠΎΠ½ΡΡ‚Ρ€ΡƒΠΊΡ†ΠΈΡŽ ΠŸΠΎΠΏΡ‹Ρ‚ΠΊΠ°...Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅, Ссли Π΅ΡΡ‚ΡŒ риск получСния Π½Π΅ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… ΠΈΠ· Π²Π½Π΅ΡˆΠ½ΠΈΡ… источников. Π­Ρ‚ΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ‚ систСмС ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠΈΡ‚ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρƒ ΠΈ Π·Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ ΠΎΠ± ошибкС Π² ΠΆΡƒΡ€Π½Π°Π» рСгистрации, вмСсто Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ "ΠΏΠ°Π΄Π°Ρ‚ΡŒ" с красным ΠΎΠΊΠ½ΠΎΠΌ.

Валидация Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… Π΄Π°Π½Π½Ρ‹Ρ… β€” ΠΏΠ΅Ρ€Π²Ρ‹ΠΉ шаг любого Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°. ΠŸΠ΅Ρ€Π΅Π΄ Π½Π°Ρ‡Π°Π»ΠΎΠΌ сравнСния ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡŒΡ‚Π΅, Ρ‡Ρ‚ΠΎ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅ Π΄Π΅ΠΉΡΡ‚Π²ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΡΠ²Π»ΡΡŽΡ‚ΡΡ массивами. Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠΉΡ‚Π΅ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΡŽ Π’ΠΈΠΏΠ—Π½Ρ‡ ΠΈΠ»ΠΈ ΠΌΠ΅Ρ‚ΠΎΠ΄ Π­Ρ‚ΠΎΠœΠ°ΡΡΠΈΠ² (Ссли доступСн Π² контСкстС), Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΡƒΠ±Π΅Π΄ΠΈΡ‚ΡŒΡΡ Π² коррСктности Ρ‚ΠΈΠΏΠΎΠ².

πŸ’‘

Π”ΠΎΠ±Π°Π²ΡŒΡ‚Π΅ Π»ΠΎΠ³ΠΈΡ€ΠΎΠ²Π°Π½ΠΈΠ΅ Π² ΠΌΠΎΠΌΠ΅Π½Ρ‚ обнаруТСния ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ различия. Π­Ρ‚ΠΎ ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ‚ быстро ΠΏΠΎΠ½ΡΡ‚ΡŒ, ΠΏΠΎΡ‡Π΅ΠΌΡƒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π²Π΅Ρ€Π½ΡƒΠ» "ΠœΠ°ΡΡΠΈΠ²Ρ‹ Π½Π΅ Ρ€Π°Π²Π½Ρ‹", Π½Π΅ пСрСбирая тысячи строк ΠΊΠΎΠ΄Π° Π²Ρ€ΡƒΡ‡Π½ΡƒΡŽ.

МоТно Π»ΠΈ ΡΡ€Π°Π²Π½ΠΈΡ‚ΡŒ массивы Ρ€Π°Π·Π½Ρ‹Ρ… Ρ‚ΠΈΠΏΠΎΠ² элСмСнтов?

ВСхничСски ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ° ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ ΠΊΠΎΠ΄, Π½ΠΎ логичСски это бСссмыслСнно. Π‘Ρ€Π°Π²Π½Π΅Π½ΠΈΠ΅ числа ΠΈ строки Π²Π΅Ρ€Π½Π΅Ρ‚ "НС Ρ€Π°Π²Π½ΠΎ". Если Ρ‚ΠΈΠΏΡ‹ элСмСнтов Π² массивах Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Π½Π½ΠΎ Ρ€Π°Π·Π½Ρ‹Π΅, сравнСниС ΠΌΠΎΠΆΠ½ΠΎ Π½Π΅ ΠΏΡ€ΠΎΠ²ΠΎΠ΄ΠΈΡ‚ΡŒ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Π·Π°Ρ€Π°Π½Π΅Π΅ извСстСн.

Как ΡΡ€Π°Π²Π½ΠΈΡ‚ΡŒ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠ΅Ρ€Π½Ρ‹Π΅ массивы Π² 1Π‘?

1Π‘ Π½Π΅ ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚ ΠΌΠ½ΠΎΠ³ΠΎΠΌΠ΅Ρ€Π½Ρ‹Π΅ массивы Π² классичСском ΠΏΠΎΠ½ΠΈΠΌΠ°Π½ΠΈΠΈ (ΠΊΠ°ΠΊ Π² C++). ΠžΠ±Ρ‹Ρ‡Π½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ массивы массивов. Для ΠΈΡ… сравнСния трСбуСтся рСкурсивный Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π±ΡƒΠ΄Π΅Ρ‚ ΡΠΏΡƒΡΠΊΠ°Ρ‚ΡŒΡΡ Π½Π° ΡƒΡ€ΠΎΠ²Π΅Π½ΡŒ Π²Π³Π»ΡƒΠ±ΡŒ ΠΏΡ€ΠΈ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΈΠΈ Π²Π»ΠΎΠΆΠ΅Π½Π½ΠΎΠ³ΠΎ массива.

ВлияСт Π»ΠΈ порядок элСмСнтов Π½Π° Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ сравнСния?

Π”Π°, ΠΏΡ€ΠΈ посимвольном ΠΈΠ»ΠΈ поэлСмСнтном сравнСнии порядок Π²Π°ΠΆΠ΅Π½. Массив [1, 2] Π½Π΅ Ρ€Π°Π²Π΅Π½ массиву [2, 1]. Если порядок Π½Π΅ Π²Π°ΠΆΠ΅Π½, массивы Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡ€Π΅Π΄Π²Π°Ρ€ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎ ΠΎΡ‚ΡΠΎΡ€Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠ΅Ρ€Π΅Π΄ сравнСниСм.

Π§Ρ‚ΠΎ быстрСС: Ρ†ΠΈΠΊΠ» "Для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ" ΠΈΠ»ΠΈ Ρ†ΠΈΠΊΠ» "По индСксам"?

Π’ соврСмСнных вСрсиях ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΡ‹ 1Π‘ Ρ€Π°Π·Π½ΠΈΡ†Π° минимальна. Однако Ρ†ΠΈΠΊΠ» "По индСксам" Π΄Π°Π΅Ρ‚ большС контроля ΠΈ позволяСт ΠΎΠ±Ρ€Π°Ρ‰Π°Ρ‚ΡŒΡΡ ΠΊ элСмСнтам ΠΎΠ±ΠΎΠΈΡ… массивов ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎ ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ индСксу, Ρ‡Ρ‚ΠΎ ΡƒΠ΄ΠΎΠ±Π½ΠΎ ΠΏΡ€ΠΈ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ΅ ΠΏΠΎΠ»Π½ΠΎΠ³ΠΎ равСнства.

Как Π½Π°ΠΉΡ‚ΠΈ Π΄ΡƒΠ±Π»ΠΈΠΊΠ°Ρ‚Ρ‹ Π²Π½ΡƒΡ‚Ρ€ΠΈ ΠΎΠ΄Π½ΠΎΠ³ΠΎ массива?

Π­Ρ‚ΠΎ частный случай сравнСния. МоТно ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π²Π»ΠΎΠΆΠ΅Π½Π½Ρ‹ΠΉ Ρ†ΠΈΠΊΠ», Π³Π΄Π΅ Π²Π½ΡƒΡ‚Ρ€Π΅Π½Π½ΠΈΠΉ Ρ†ΠΈΠΊΠ» начинаСтся с индСкса внСшнСго + 1. Π›ΠΈΠ±ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π’Π°Π±Π»ΠΈΡ†Ρƒ Π—Π½Π°Ρ‡Π΅Π½ΠΈΠΉ с Π³Ρ€ΡƒΠΏΠΏΠΈΡ€ΠΎΠ²ΠΊΠΎΠΉ ΠΈ подсчСтом количСства строк.