memerlukan algoritma untuk menciutkan rentang netblock ke dalam daftar rentang superset

Matematika-fu saya mengecewakan saya! Saya memerlukan cara yang efisien untuk mengurangi rentang jaringan menjadi superset, misalnya. jika saya memasukkan daftar rentang IP:

  • 1.1.1.1 to 2.2.2.5
  • 1.1.1.2 to 2.2.2.4
  • 10.5.5.5 to 155.5.5.5
  • 10.5.5.6 to 10.5.5.7

Saya ingin mengembalikan rentang berikut:

  • 1.1.1.1 to 2.2.2.5
  • 10.5.5.5 to 155.5.5.5

Catatan: daftar masukan tidak diurutkan (walaupun bisa saja?). Cara naif untuk melakukan ini adalah dengan memeriksa setiap rentang dalam daftar untuk melihat apakah rentang input x adalah subset, dan jika ya, BUKAN masukkan rentang x. Namun, setiap kali Anda memasukkan rentang baru, rentang tersebut mungkin merupakan superset dari rentang yang sudah ada, jadi Anda harus memeriksa rentang yang ada untuk melihat apakah rentang tersebut dapat diciutkan (misalnya, dihapus dari daftar saya).


algorithm superset
person Jen A    schedule 29.09.2008    source sumber
comment
Apakah rentangnya akan terputus-putus? Jika tidak, bagaimana Anda ingin algoritme Anda menangani rentang yang tumpang tindih, yang banyak di antaranya dapat menjadi bagian dari subrentang?   -  person HenryR    schedule 29.09.2008
comment
Apa masalah dengan penggunaan algoritma 'naif' yang Anda jelaskan? Tampaknya baik-baik saja bagi saya...   -  person    schedule 29.09.2008
comment
Pertanyaan bagus! Pengguna dapat memasukkan rentang apa pun yang mereka inginkan, jadi tidak ada jaminan bahwa rentang tersebut akan terputus-putus. Sebenarnya akan lebih baik jika semua rentang yang berdekatan dapat diciutkan menjadi satu.   -  person Jen A    schedule 29.09.2008
comment
Bagi MikeF: cara yang naif bisa jadi sangat lambat, jika saya harus membandingkan setiap item yang ada dalam daftar setiap kali saya memasukkan. Kami memiliki beberapa pelanggan dengan rentang › 40k (dan ingin menambahkan lebih banyak!). Saya tidak ingin melakukan perbandingan 40k untuk melakukan penyisipan.   -  person Jen A    schedule 29.09.2008
comment
Cara yang naif, seperti dijelaskan, juga akan gagal menangani kasus di mana dua rentang tumpang tindih tanpa satu rentang sepenuhnya termuat oleh rentang lainnya.   -  person Dave Sherohman    schedule 29.09.2008

Jawaban (4)


arrow_upward
17
arrow_downward

Ini adalah gabungan perhitungan segmen. Algoritme optimal (dalam O(nlog(n))) terdiri dari melakukan hal berikut:

  1. urutkan semua titik akhir (titik awal dan akhir) dalam daftar L (setiap titik akhir harus mengetahui segmen miliknya). Jika titik akhir sama dengan titik awal, maka titik awal harus dianggap lebih kecil dari titik akhir.
  2. telusuri daftar yang diurutkan L dari kiri ke kanan dan pertahankan nomor LE-RE, dengan LE adalah jumlah titik akhir kiri yang telah Anda lewati, dan RE adalah jumlah titik akhir kanan yang telah Anda lewati.
  3. setiap kali LE-RE mencapai nol, Anda berada di akhir gabungan segmen-segmen yang terhubung, dan Anda mengetahui bahwa gabungan segmen-segmen yang pernah Anda lihat sebelumnya (sejak kembali ke nol sebelumnya) adalah satu superset.
  4. jika Anda juga mempertahankan min dan max, antara masing-masing pengembalian ke nol, Anda memiliki batasan superset.

Pada akhirnya, Anda mendapatkan daftar superset terpisah yang diurutkan. Namun, dua superset A dan B dapat bertetangga (titik akhir A tepat sebelum titik awal B). Jika Anda ingin A dan B digabungkan, Anda dapat melakukannya dengan langkah pascapemrosesan sederhana, atau dengan sedikit memodifikasi langkah 3: ketika LE-RE mencapai nol, Anda akan menganggapnya sebagai akhir dari sebuah superset hanya jika elemen berikutnya di L bukan penerus langsung elemen Anda saat ini.

person Camille    schedule 29.09.2008

arrow_upward
5
arrow_downward

Anda tahu bahwa Anda dapat dengan mudah mengubah alamat IPv4 menjadi angka int (angka int32), bukan? Bekerja dengan angka int jauh lebih mudah. Jadi pada dasarnya setiap alamat adalah angka dalam rentang 0 hingga 2^32. Setiap rentang memiliki nomor awal dan nomor akhir. Teladan Anda

1.1.1.1 to 2.2.2.5
1.1.1.2 to 2.2.2.4

dapat ditulis sebagai

16,843,009 to 33,686,021
16,843,010 to 33,686,020

Jadi cukup mudah untuk melihat apakah satu rentang berada dalam rentang lainnya. Suatu rentang sepenuhnya berada dalam rentang lainnya jika kondisi berikut diberikan

startIP2 >= startIP1 && startIP2 <= endIP1 &&
endIP1 >= startIP1 && endIP2 <= endIP1

Dalam hal ini rentang startIP2-endIP2 sepenuhnya berada dalam startIP1-endIP1. Jika hanya baris pertama yang benar, maka startIP2 berada dalam rentang startIP1-endIP1, namun akhir berada di luar rentang tersebut. Jika hanya baris kedua yang benar, maka IP akhir berada dalam jangkauan, namun IP awal berada di luar jangkauan. Dalam hal ini, jika hanya satu baris yang benar, Anda perlu memperluas jangkauannya di awal atau di akhir. Jika kedua garis salah, rentangnya benar-benar terputus-putus, dalam hal ini keduanya merupakan rentang yang sepenuhnya independen.

person Mecki    schedule 30.09.2008

arrow_upward
0
arrow_downward

Yang perlu Anda lakukan hanyalah memeriksa rentang apakah ada yang tumpang tindih. Jika dua rentang tumpang tindih, keduanya akan digabungkan menjadi satu rentang. Rentang tumpang tindih jika sisi kanan suatu rentang lebih besar dari sisi kiri rentang lainnya.

person paxos1977    schedule 29.09.2008
comment
Menurut definisi Anda, 10.1.1.0-10.2.2.255 (satu rentang) tumpang tindih dengan 4.4.4.0-4.4.4.255 (rentang lain). - person tzot; 29.09.2008

arrow_upward
0
arrow_downward

Baiklah, rekan kerja saya memberikan jawaban ini, yang menurut saya cukup bagus. Beri tahu saya jika Anda melihat masalah apa pun:

  • Urutkan rentang IP berdasarkan StartingIP
  • For each row "x" to insert:
    • If there is a previous row "y" in the list, fetch:
      • If x and y are contiguous, extend y to x's EndingIP
      • Lain jika x.StartingIP ‹= y.StartingIP dan x.EndingIP > y.EndingIP, perpanjang y ke x.EndingIP
      • Jika tidak, jika x adalah bagian dari y, jangan lakukan apa pun
      • Jika tidak, buat rentang baru
    • Jika tidak, buat rentang baru dan masukkan ke dalam daftar
person Jen A    schedule 29.09.2008
comment
Ya, sesuatu seperti ini pasti akan berhasil. - person ; 29.09.2008
comment
BTW, tampaknya lebih mudah untuk mengoperasikan seluruhnya pada satu daftar daripada membuat daftar kedua dari daftar rentang awal. - person ; 29.09.2008