Cheksiz ro'yxatlarning kesishishi

Hisoblashni nazariyadan bilaman, ikkita cheksiz ro'yxatlarning kesishuvini olish mumkin, ammo men buni Haskellda ifodalash uchun bir usul topa olmayapman.

Ikkinchi ro'yxat cheksiz bo'lsa, an'anaviy usul muvaffaqiyatsiz bo'ladi, chunki siz butun vaqtni birinchi ro'yxatdagi mos bo'lmagan element uchun tekshirasiz.

Misol:

let ones = 1 : ones -- an unending list of 1s
intersect [0,1] ones

1 elementi uchun ones tekshiruvini hech qachon to'xtatmaydi, chunki bu hech qachon 1 ni bermaydi.

Muvaffaqiyatli usul har bir ro'yxatning har bir elementini oxirgi vaqtlarda ko'rishni ta'minlashi kerak.

Ehtimol, bu ikkala ro'yxatlar orqali takrorlash va har bir ro'yxatda bir-biriga nisbatan oldindan ko'rilgan barcha elementlarni tekshirish uchun taxminan teng vaqt sarflash mumkin.

Mumkin bo'lgan taqdirda, ro'yxatlardagi dublikatlarni ham e'tibordan chetda qoldirishni xohlayman, chunki vaqti-vaqti bilan kerak bo'lsa, lekin bu talab emas.

7
Qanday natija siz ikkita cheksiz ro'yxatlarning kesishuvini olishingiz mumkinligini aytadi? Bu shunga o'xshash haqiqat emasligiga juda ishonaman.
qo'shib qo'ydi muallif leftaroundabout, manba
Savollar echim emas, balki muammo ni o'z ichiga olishi kerak. Agar siz boshqa va/yoki yaxshi javob bera olganingizni his qilsangiz, iltimos, o'z savolingizga javob bering (buni bajaring!). Agar savolda javob berilsa, foydalanuvchilar ikkalasi uchun alohida ovoz berishga qodir emas (masalan, savolni o'zi yoki viceversa-ni ko'tarmasdan "yaxshi-yaxshi savol" ga yaxshi javob berishni istashadi).
qo'shib qo'ydi muallif Bakuriu, manba
@leftaroundoutout: siz ortib boruvchi chegaradan foydalanishingiz mumkin.
qo'shib qo'ydi muallif Willem Van Onsem, manba
@AJFarmar bu "algoritm" nimani anglatadi? Men hech kimni bermadim
qo'shib qo'ydi muallif Zoey Hewll, manba
Biroz o'xshash va, ehtimol, oddiy misol uchun, shuni takrorlash uchun ratsional sonlarning hisobga olinishi yoki bu havola
qo'shib qo'ydi muallif Zoey Hewll, manba
@ZoeyHewll Bu mumkin, lekin bu algoritm bilan emas.
qo'shib qo'ydi muallif AJFarmar, manba

6 javoblar

koinot paketining Cartesian mahsuloti operatori biz ushbu layneri yozishimiz mumkin:

import Data.Universe.Helpers

isect :: Eq a => [a] -> [a] -> [a]
xs `isect` ys = [x | (x, y) <- xs +*+ ys, x == y]

Uni ghci bilan sinab ko'ring:

> take 10 $ [0,2..] `isect` [0,3..]
[0,6,12,18,24,30,36,42,48,54]

Agar kirish ro'yxatlarida bunday bo'lmasa, bu dastur hech qanday takroriy nusxa olmaydi; lekin agar qilsalar, sevimli kodni tozalash vositasida yoki ishqiy deb chaqirganingizdan oldin yoki keyin qo'ng'iroq qilishingiz mumkin. Masalan, nub bilan yozishingiz mumkin

> nub ([0,1] `isect` repeat 1)
[1

va keyin kompyuteringizni juda yaxshi isitish, chunki u etarli darajada chuqurroq bo'lsa, bu ikkinchi ro'yxatda 0 bo'lmasligi mumkin.

Bu yondashuv Deyvid Fletcherga qaraganda ancha tezroq bo'lib, juda ko'p sonli nusxalar ishlab chiqaradi va Willem Van Onsemdan ko'ra yangi qadriyatlarni tezroq ishlab chiqaradi va ro'yxatlar freestyle uslubi kabi saralanadi deb hisoblamaydi (lekin shunga qarab, erkin uslublardan ko'ra bunday ro'yxatlar bo'yicha juda sekinroq).

9
qo'shib qo'ydi

Bir g'oya, incrementing boundaries dan foydalanish mumkin. Birinchi navbatda muammoni bir oz yengillatib ko'raylik: takroriy qiymatlarni berishga ruxsat beriladi. Bunday holatda siz quyidagilarni ishlatishingiz mumkin:

import Data.List (intersect)

intersectInfinite :: Eq a => [a] -> [a] -> [a]
intersectInfinite = intersectInfinite' 1
    where intersectInfinite' n = intersect (take n xs) (take n ys) ++ intersectInfinite' (n+1)

Boshqa so'zlar bilan aytamizki,

A∩B = A1∩B1 ∪ A2∩B2 ∪ ... ∪ ...

A 1 bilan A birinchi i elementlarini o'z ichiga olgan yechim mavjud. (Ha, to'plamda tartib yo'q, lekin buyurtma). To'siq kamroq elementlari bo'lsa, u holda butun to'siq qaytariladi.

C ( i katalogida) va B (Index j c segmentida (indeks emas) max (i, j) sifatida chiqariladi.

Shunday qilib, ushbu ro'yxatlar cheklangan yoki yo'qligiga qaramasdan har doim cheksiz ro'yxatni (cheksiz miqdorda takroriy) yaratadi. Faqatgina istisno - bu siz bo'sh ro'yxatni berganingizda, u holda bu abadiy qabul qilinadi. Shunga qaramay, biz bu erda kesishgan har bir element kamida bir marta chiqarilishini ta'minladik.

Natijani oxirigacha qilish (agar berilgan ro'yxatlar cheklangan bo'lsa)

Endi biz ta'rifimizni yaxshiroq qilishimiz mumkin. Birinchidan, biz take , takeFinite (ilg'or, lekin juda ham foydali emasligini aniq belgilasak) ni yanada rivojlangan bir versiyasini yaratamiz:

takeFinite :: Int -> [a] -> (Bool,[a])
takeFinite _ [] = (True,[])
takeFinite 0 _  = (False,[])
takeFinite n (x:xs) = let (b,t) = takeFinite (n-1) xs in (b,x:t)

Keling, ikkala ro'yxatlarini oxirigacha yetkazilgunga qadar biz uni yanada chuqurroq chuqurlashtirishimiz mumkin:

intersectInfinite :: Eq a => [a] -> [a] -> [a]
intersectInfinite = intersectInfinite' 1

intersectInfinite' :: Eq a => Int -> [a] -> [a] -> [a]
intersectInfinite' n xs ys | fa && fb = intersect xs ys
                           | fa = intersect ys xs
                           | fb = intersect xs ys
                           | otherwise = intersect xfa xfb ++ intersectInfinite' (n+1) xs ys
    where (fa,xfa) = takeFinite n xs
          (fb,xfb) = takeFinite n ys

Ikkala ro'yxat ham cheklangan bo'lsa-da, endi ko'p sonli nusxalar ishlab chiqariladi. Bu muammoni hal qilishning aniq usullari mavjud (agar ko'proq vaqt bo'lsa, yangilanadi).

6
qo'shib qo'ydi
@ZoeyHewll Bunday ro'yxatni «bo'sh» deb nomlash haqiqatdan ham to'g'ri emas. [] - bu bo'sh ro'yxat. Doimiy ravishda ishlaydigan va abadiy ishga tushirilgan dastur qiymati (bu erda bu erda bo'lishi kerak bo'lgan bo'sh ro'yxat) qiymatini ifodalaydi, bu qiymat pastni ifodalaydi.
qo'shib qo'ydi muallif user2407038, manba
@ZoeyHewll Lekin Haskell ro'yxatlari mumkin aslida abadiy bo'lishi mumkin ... bu ular haqida mulohaza yuritish uchun 'qulay' emas. Har qanday dangal rekordif ma'lumotlar tuzilishi deyarli barcha dangasalik nuqtasi bo'lgan cheksiz qiymatlarni o'z ichiga olishi mumkin. Matematik nuqtadan aniq bir nuqtai nazar - qiymatni qaytarib olish uchun doimiy hisoblangan hisob-kitob pastki ( undefined ), chunki bunday hisoblashni () ajratish uchun mutlaqo hech qanday usul yo'q «hisoblashni» rasmiylashtirgan nazariyada) hech narsa qilmayotgan narsalardan biri. (Bu odatda "to'xtash muammosi" deb nomlanadi)
qo'shib qo'ydi muallif user2407038, manba
@ZoeyHewll: ha, rahmat. Men bu muammoni bir oz ko'proq hal qildim, deb o'ylayman, ammo hal etilishi hali ham yaxshilanishi mumkin.
qo'shib qo'ydi muallif Willem Van Onsem, manba
@ user2407038 Lekin men taglikning ta'rifini tushunaman va bu hisob-kitob haqida nima gapirayotganingizni sezaman. Ishonchim komilki, hisoblangan ma'lumot strukturasi cheksiz emas, balki aslida cheksiz bo'lishi mumkin, lekin men qanday qilib dangasa ishlamayapti va qanday qilib bu haqda mulohaza yuritishingiz haqida ko'p narsa bilmayman nazariy jihatdan
qo'shib qo'ydi muallif Zoey Hewll, manba
@ user2407038 To'xtash muammosi haqida bilaman. Men "matematik nuqtai nazar" deb aytganda, nazariy nazariya kabi emas, balki hisoblash nazariyasi kabi emas. Ikkita cheksiz ro'yxatni kesish vaqtini hisoblashning iloji bo'lmasa-da, matematik tarzda siz ularning o'zaro mutlaqo mutlaqo mutlaqo bilishlarini bilsangiz, ularning kesishmasi bo'shligini belgilashingiz mumkin.
qo'shib qo'ydi muallif Zoey Hewll, manba
@ user2407038 Men qanaqa tubni bilmayman, lekin matematik nuqtai nazardan qaraydigan bo'lsak ham, kompyuter oxir-oqibat kesishgan nuqtani hisoblab chiqishi mumkin bo'lsa ham, faqat bo'sh ro'yxatni qaytaradi. Ro'yxatlar aslida cheksiz, cheksiz va cheksiz bo'lgan narsalar kabi ko'rinadi, ammo ularni abadiy deb atash qulay.
qo'shib qo'ydi muallif Zoey Hewll, manba
Tuzatish: ro'yxat cheksiz yoki bo'sh bo'lishi mumkin. Agar biron bir kesishma bo'lsa, u cheksiz bo'ladi, lekin hech qanday umumiy elementlar bo'lmasa, u bo'sh bo'ladi (albatta, bo'sh bo'lsa, u faqat har qanday usulda kafolatlanadi)
qo'shib qo'ydi muallif Zoey Hewll, manba

Mana bir yo'l. Har x uchun, biz o'z ichiga olgan mayblar ro'yxatini tuzamiz Faqatgina x ys manzilida faqat x . Keyin hammamiz bir-birimizga qo'shilamiz Ushbu ro'yxatlar.

isect :: Eq a => [a] -> [a] -> [a]
isect xs ys = (catMaybes . foldr interleave [] . map matches) xs
  where
    matches x = [if x == y then Just x else Nothing | y <- ys]

interleave :: [a] -> [a] -> [a]
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs

Ehtimol, u qandaydir adolatli interleaving yordamida yaxshilanishi mumkin - quyidagi misolda juda sekin (chunki menimcha) bu eksponentsial miqdordagi ishni bajaradi.

> take 10 (isect [0..] [0,2..])
[0,2,4,6,8,10,12,14,16,18]
5
qo'shib qo'ydi
@DavidFletcher Sizning javobingiz eksponentsiyasiz haqsan. pastki intervalgacha [] $ takrorlash <$> [1 ..] , har bir ikkinchi element 1 , har 4-element 2 2 ^ n elementi n hisoblanadi. Ya'ni, kesishish hisobida, birinchi ro'yxatning har bir elementi (boshqa ro'yxat elementlariga nisbatan) yarmigacha tez-tez tekshiriladi.
qo'shib qo'ydi muallif Zoey Hewll, manba
@DanielWagner yarmarkasi. + * + ilovasini ko'rmaganman. Biroq, mening qabul qilingan javobim bo'yicha men eng foydali topdim »deb qo'yaman
qo'shib qo'ydi muallif Zoey Hewll, manba
@DanielWagner qaerda? Bundan tashqari, menda osonlikcha (men uchun) o'qilishi mumkin, ifodali funktsiyani ishlab chiqarish uchun foldr interleave [] ni diagonal bilan o'zgartiraman. Sizningcha, qisqagina bo'lsa-da, men izoh berish uchun ko'proq ishni talab qilaman.
qo'shib qo'ydi muallif Zoey Hewll, manba
@DanielWagner Qani, diagonal to'liq fikrlashning ideal usulidir!
qo'shib qo'ydi muallif Zoey Hewll, manba
Men hozirda qanday qilib amalga oshirilganligini tushunolmayapman, chunki interleavingni qanday yaxshilashni tushunmayman. Kodni kuzatishim mumkin, lekin kodni foldr ning natijalari elementlarning tartibida bo'ladi, deb tushunolmayman
qo'shib qo'ydi muallif Zoey Hewll, manba
Xo'sh, siz yana bitta ro'yxat orqali yechmoqdasiz va boshqa o'yinlarni nazorat qilishingiz mumkin, ammo natijalarni bir-biriga ulashgansiz ...
qo'shib qo'ydi muallif Zoey Hewll, manba
diagonal bilan tanishib chiqing.
qo'shib qo'ydi muallif Daniel Wagner, manba
@ZoeyHewll Keyin nima uchun bu javobni qabul qildingiz? Hatto diagonal dan foydalanmasangiz, meniki esa ...
qo'shib qo'ydi muallif Daniel Wagner, manba
@ZoeyHewll o'ngda bu erda : xs + * + ys = diagonal [[(x, y) | x <- xs] | y <- ys] ni bosing
qo'shib qo'ydi muallif Daniel Wagner, manba
@ZoeyHewll Aytgancha, + * + uchun boshqa belgilaydigan chiziqdagi sharh ushbu dasturning buggy ekanligini ta'kidlaydi: ishq [0 ..] [] bilan solishtiring mening amalga oshirish va uning. Shu sababli kutubxonani qayta ishlatish juda muhimdir: siz o'zingiz o'ylaydigan barcha ishlarni bajarishdan oldin hech kim hech qachon qilmagan barcha bugfixalarga ta'sir qilasiz.
qo'shib qo'ydi muallif Daniel Wagner, manba
birlashma ["a1", "a2", "a3", "a4", "a5", a6 "] (interleave [ "b1", "b2", "b3"] ["c1", "c2", "c3"]) har ikkinchi element a .
qo'shib qo'ydi muallif David Fletcher, manba

Agar ro'yxatlardagi elementlar buyurtma qilingan bo'lsa, buni oson qilishingiz mumkin.

intersectOrd :: Ord a => [a] -> [a] -> [a]
intersectOrd [] _ = []
intersectOrd _ [] = []
intersectOrd (x:xs) (y:ys) = case x `compare` y of
    EQ -> x : intersectOrd xs ys
    LT -> intersectOrd xs (y:ys)
    GT -> intersectOrd (x:xs) ys
4
qo'shib qo'ydi
Shuningdek qarang: Dash ma'lumotlar to'plamining to'plami; bu paket buyurtma (va potentsial cheksiz) ro'yxatlar ustida ishlaydigan ko'plab boshqa qulay operatsiyalarni ham beradi.
qo'shib qo'ydi muallif Daniel Wagner, manba

Here's yet another alternative, leveraging Control.Monad.WeightedSearch

import Control.Monad (guard)
import Control.Applicative
import qualified Control.Monad.WeightedSearch as W

Avval biz ro'yxat ichida qazish uchun narxni belgilab olamiz. Tailga kirish uchun 1 ta qo'shimcha xarajat bor. Bu ikkita cheksiz ro'yxatlar orasida adolatli rejani ta'minlaydi.

eachW :: [a] -> W.T Int a
eachW = foldr (\x w -> pure x <|> W.weight 1 w) empty

Shunda biz cheksiz ro'yxatlarni e'tiborsiz qoldiramiz.

intersection :: [Int] -> [Int] -> [Int]
intersection xs ys = W.toList $ do
   x <- eachW xs
   y <- eachW ys
   guard (x==y)
   return y

MonadComprehensions bilan yanada yaxshi:

intersection2 :: [Int] -> [Int] -> [Int]
intersection2 xs ys = W.toList [ y | x <- eachW xs, y <- eachW ys, x==y ]
2
qo'shib qo'ydi

Biznes

Quyidagi amalni qo'llash bilan yakun topdim; Deyvid Fletcher tomonidan berilgan javobning engil o'zgarishi:

isect :: Eq a => [a] -> [a] -> [a]
isect [] = const [] -- don't bother testing against an empty list
isect xs = catMaybes . diagonal . map matches
    where matches y = [if x == y then Just x else Nothing | x <- xs]

Bu replikatsiyalarni filtrlash uchun nub bilan kengaytirilishi mumkin:

isectUniq :: Eq a => [a] -> [a] -> [a]
isectUniq xs = nub . isect xs

Izoh

Of the line isect xs = catMaybes . diagonal . map matches

(map matches) ys computes a list of lists of comparisons between elements of xs and ys, where the list indices specify the indices in ys and xs respectively: i.e (map matches) ys !! 3 !! 0 would represent the comparison of ys !! 3 with xs !! 0, which would be Nothing if those values differ. If those values are the same, it would be Just that value.

diagonals takes a list of lists and returns a list of lists where the nth output list contains an element each from the first n lists. Another way to conceptualise it is that (diagonals . map matches) ys !! n contains comparisons between elements whose indices in xs and ys sum to n.
diagonal is simply a flat version of diagonals (diagonal = concat diagonals)

Shuning uchun (diagonal map mapped) ys elementlari xs va ys elementlari o'rtasidagi taqqoslashlar ro'yxati bo'lib, ys va xs xodimlari elementlari solishtiriladi; bu erta elementlar o'rta elementlar bir-biri bilan taqqoslanadigan bir xil ustunlikka ega bo'lgan keyingi elementlarga solishtiriladi.

(catMaybes . diagonal . map matches) ys is a list of only the elements which are in both lists, where the elements are approximately sorted by the sum of the indices of the two elements being compared.

Note
(diagonal . map (catMaybes . matches)) ys does not work: catMaybes . matches only yields when it finds a match, instead of also yielding Nothing on no match, so the interleaving does nothing to distribute the work.

To contrast, in the chosen Biznes, the interleaving of Nothing and Just values by diagonal means that the program divides its attention between 'searching' for multiple different elements, not waiting for one to succeed; whereas if the Nothing values are removed before interleaving, the program may spend too much time waiting for a fruitless 'search' for a given element to succeed.

Therefore, we would encounter the same problem as in the original question: while one element does not match any elements in the other list, the program will hang; whereas the chosen Biznes will only hang while no matches are found for any elements in either list.

0
qo'shib qo'ydi