fastest way search ip in large ip/subnet list on golang?
-1
please help me solve next task in fastest possible way
i have a large list of ip/subnets like ...
35.132.199.128/27
8.44.144.248/32
87.117.185.193
45.23.45.45
etc
and i'll need to find some ip in that list fastes as possible in go.
when i try use slice of strings and range, it was very slow on large list.
may i use map, like map[string]string, and its look usable but only for ip checking, not for subnet checking.
anyone can help me with solving this task? thanks.
my code
func (app *application) validateIP(ip string) bool {
for _, item := range app.IPList {
itemIsIP := net.ParseIP(item)
if itemIsIP != nil {
if ip == itemIsIP.String() {
return true
}
continue
}
_, itemNet, err := net.ParseCIDR(item)
if err != nil {
log.Printf("[ERROR] %+v", err)
}
checkedIP := net.ParseIP(ip)
if itemNet.Contains(checkedIP) {
return true
}
}
return false
}
go
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
add a comment |
-1
please help me solve next task in fastest possible way
i have a large list of ip/subnets like ...
35.132.199.128/27
8.44.144.248/32
87.117.185.193
45.23.45.45
etc
and i'll need to find some ip in that list fastes as possible in go.
when i try use slice of strings and range, it was very slow on large list.
may i use map, like map[string]string, and its look usable but only for ip checking, not for subnet checking.
anyone can help me with solving this task? thanks.
my code
func (app *application) validateIP(ip string) bool {
for _, item := range app.IPList {
itemIsIP := net.ParseIP(item)
if itemIsIP != nil {
if ip == itemIsIP.String() {
return true
}
continue
}
_, itemNet, err := net.ParseCIDR(item)
if err != nil {
log.Printf("[ERROR] %+v", err)
}
checkedIP := net.ParseIP(ip)
if itemNet.Contains(checkedIP) {
return true
}
}
return false
}
go
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
1
convert the ip + CIDR mask to 5 bytes and store them in a uint, then use the resultant number as a map key. If you want to find which range a particular ip falls in then that would be slightly more complicated
– Vorsprung
Nov 20 '18 at 16:38
What is a "very large list"? Are you using a binary search? Are you certain the code is slow because of iterating over the list, or because you're converting every string to an ip&mask for every comparison?
– JimB
Nov 20 '18 at 16:44
at this moment in list 200k records, updated first post with code
– Rapid Code Lab
Nov 20 '18 at 16:50
You're parsing every string for every comparison. Wouldn't it make sense to parse those ahead of time first and see if that is performant enough? (It also might help to show where the bottleneck is from some real benchmarks)
– JimB
Nov 20 '18 at 16:58
1
I think a trie would be a good data structure to use here, since you're essentially doing a prefix search. I don't have a ready-made package to recommend, although github.com/derekparker/trie looks decent.
– Mark Plotnick
Nov 20 '18 at 17:02
add a comment |
-1
-1
-1
please help me solve next task in fastest possible way
i have a large list of ip/subnets like ...
35.132.199.128/27
8.44.144.248/32
87.117.185.193
45.23.45.45
etc
and i'll need to find some ip in that list fastes as possible in go.
when i try use slice of strings and range, it was very slow on large list.
may i use map, like map[string]string, and its look usable but only for ip checking, not for subnet checking.
anyone can help me with solving this task? thanks.
my code
func (app *application) validateIP(ip string) bool {
for _, item := range app.IPList {
itemIsIP := net.ParseIP(item)
if itemIsIP != nil {
if ip == itemIsIP.String() {
return true
}
continue
}
_, itemNet, err := net.ParseCIDR(item)
if err != nil {
log.Printf("[ERROR] %+v", err)
}
checkedIP := net.ParseIP(ip)
if itemNet.Contains(checkedIP) {
return true
}
}
return false
}
go
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
please help me solve next task in fastest possible way
i have a large list of ip/subnets like ...
35.132.199.128/27
8.44.144.248/32
87.117.185.193
45.23.45.45
etc
and i'll need to find some ip in that list fastes as possible in go.
when i try use slice of strings and range, it was very slow on large list.
may i use map, like map[string]string, and its look usable but only for ip checking, not for subnet checking.
anyone can help me with solving this task? thanks.
my code
func (app *application) validateIP(ip string) bool {
for _, item := range app.IPList {
itemIsIP := net.ParseIP(item)
if itemIsIP != nil {
if ip == itemIsIP.String() {
return true
}
continue
}
_, itemNet, err := net.ParseCIDR(item)
if err != nil {
log.Printf("[ERROR] %+v", err)
}
checkedIP := net.ParseIP(ip)
if itemNet.Contains(checkedIP) {
return true
}
}
return false
}
go
go
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
edited Nov 20 '18 at 16:54
Rapid Code Lab
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
asked Nov 20 '18 at 16:28
Rapid Code LabRapid Code Lab
13
13
1
convert the ip + CIDR mask to 5 bytes and store them in a uint, then use the resultant number as a map key. If you want to find which range a particular ip falls in then that would be slightly more complicated
– Vorsprung
Nov 20 '18 at 16:38
What is a "very large list"? Are you using a binary search? Are you certain the code is slow because of iterating over the list, or because you're converting every string to an ip&mask for every comparison?
– JimB
Nov 20 '18 at 16:44
at this moment in list 200k records, updated first post with code
– Rapid Code Lab
Nov 20 '18 at 16:50
You're parsing every string for every comparison. Wouldn't it make sense to parse those ahead of time first and see if that is performant enough? (It also might help to show where the bottleneck is from some real benchmarks)
– JimB
Nov 20 '18 at 16:58
1
I think a trie would be a good data structure to use here, since you're essentially doing a prefix search. I don't have a ready-made package to recommend, although github.com/derekparker/trie looks decent.
– Mark Plotnick
Nov 20 '18 at 17:02
add a comment |
1
convert the ip + CIDR mask to 5 bytes and store them in a uint, then use the resultant number as a map key. If you want to find which range a particular ip falls in then that would be slightly more complicated
– Vorsprung
Nov 20 '18 at 16:38
What is a "very large list"? Are you using a binary search? Are you certain the code is slow because of iterating over the list, or because you're converting every string to an ip&mask for every comparison?
– JimB
Nov 20 '18 at 16:44
at this moment in list 200k records, updated first post with code
– Rapid Code Lab
Nov 20 '18 at 16:50
You're parsing every string for every comparison. Wouldn't it make sense to parse those ahead of time first and see if that is performant enough? (It also might help to show where the bottleneck is from some real benchmarks)
– JimB
Nov 20 '18 at 16:58
1
I think a trie would be a good data structure to use here, since you're essentially doing a prefix search. I don't have a ready-made package to recommend, although github.com/derekparker/trie looks decent.
– Mark Plotnick
Nov 20 '18 at 17:02
1
1
convert the ip + CIDR mask to 5 bytes and store them in a uint, then use the resultant number as a map key. If you want to find which range a particular ip falls in then that would be slightly more complicated
– Vorsprung
Nov 20 '18 at 16:38
convert the ip + CIDR mask to 5 bytes and store them in a uint, then use the resultant number as a map key. If you want to find which range a particular ip falls in then that would be slightly more complicated
– Vorsprung
Nov 20 '18 at 16:38
What is a "very large list"? Are you using a binary search? Are you certain the code is slow because of iterating over the list, or because you're converting every string to an ip&mask for every comparison?
– JimB
Nov 20 '18 at 16:44
What is a "very large list"? Are you using a binary search? Are you certain the code is slow because of iterating over the list, or because you're converting every string to an ip&mask for every comparison?
– JimB
Nov 20 '18 at 16:44
at this moment in list 200k records, updated first post with code
– Rapid Code Lab
Nov 20 '18 at 16:50
at this moment in list 200k records, updated first post with code
– Rapid Code Lab
Nov 20 '18 at 16:50
You're parsing every string for every comparison. Wouldn't it make sense to parse those ahead of time first and see if that is performant enough? (It also might help to show where the bottleneck is from some real benchmarks)
– JimB
Nov 20 '18 at 16:58
You're parsing every string for every comparison. Wouldn't it make sense to parse those ahead of time first and see if that is performant enough? (It also might help to show where the bottleneck is from some real benchmarks)
– JimB
Nov 20 '18 at 16:58
1
1
I think a trie would be a good data structure to use here, since you're essentially doing a prefix search. I don't have a ready-made package to recommend, although github.com/derekparker/trie looks decent.
– Mark Plotnick
Nov 20 '18 at 17:02
I think a trie would be a good data structure to use here, since you're essentially doing a prefix search. I don't have a ready-made package to recommend, although github.com/derekparker/trie looks decent.
– Mark Plotnick
Nov 20 '18 at 17:02
add a comment |
1 Answer
1
active
oldest
votes
-1
We solved this problem in our project:
isIPV4inCIDRList("35.132.199.128", string{"35.132.199.128/27"})
func isIPV4inCIDRList(ip byte, list string) bool {
for i := 0; i < 32; i++ {
sm := strconv.Itoa(i)
m, _ := mask(sm, 4)
inv := andIP(ip, byte(m))
if len(inv) == 0 {
continue
}
for _, cidr := range list {
if cidr == inv.String() + "/" + sm {
return true
}
}
}
return false
}
func andIP(ip, mask byte) net.IP {
inv := net.IP{}
for i, v := range ip {
inv = append(inv, mask[i]&v)
}
return inv
}
// Bigger than we need, not too big to worry about overflow
const big = 0xFFFFFF
// Decimal to integer.
// Returns number, characters consumed, success.
func dtoi(s string) (n int, i int, ok bool) {
n = 0
for i = 0; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
n = n*10 + int(s[i]-'0')
if n >= big {
return big, i, false
}
}
if i == 0 {
return 0, 0, false
}
return n, i, true
}
func mask(m string, iplen int) (net.IPMask, error) {
n, i, ok := dtoi(m)
if !ok || i != len(m) || n < 0 || n > 8*iplen {
return nil, &net.ParseError{Type: "CIDR address"}
}
return net.CIDRMask(n, 8*iplen), nil
}
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53397369%2ffastest-way-search-ip-in-large-ip-subnet-list-on-golang%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
-1
We solved this problem in our project:
isIPV4inCIDRList("35.132.199.128", string{"35.132.199.128/27"})
func isIPV4inCIDRList(ip byte, list string) bool {
for i := 0; i < 32; i++ {
sm := strconv.Itoa(i)
m, _ := mask(sm, 4)
inv := andIP(ip, byte(m))
if len(inv) == 0 {
continue
}
for _, cidr := range list {
if cidr == inv.String() + "/" + sm {
return true
}
}
}
return false
}
func andIP(ip, mask byte) net.IP {
inv := net.IP{}
for i, v := range ip {
inv = append(inv, mask[i]&v)
}
return inv
}
// Bigger than we need, not too big to worry about overflow
const big = 0xFFFFFF
// Decimal to integer.
// Returns number, characters consumed, success.
func dtoi(s string) (n int, i int, ok bool) {
n = 0
for i = 0; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
n = n*10 + int(s[i]-'0')
if n >= big {
return big, i, false
}
}
if i == 0 {
return 0, 0, false
}
return n, i, true
}
func mask(m string, iplen int) (net.IPMask, error) {
n, i, ok := dtoi(m)
if !ok || i != len(m) || n < 0 || n > 8*iplen {
return nil, &net.ParseError{Type: "CIDR address"}
}
return net.CIDRMask(n, 8*iplen), nil
}
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
add a comment |
-1
We solved this problem in our project:
isIPV4inCIDRList("35.132.199.128", string{"35.132.199.128/27"})
func isIPV4inCIDRList(ip byte, list string) bool {
for i := 0; i < 32; i++ {
sm := strconv.Itoa(i)
m, _ := mask(sm, 4)
inv := andIP(ip, byte(m))
if len(inv) == 0 {
continue
}
for _, cidr := range list {
if cidr == inv.String() + "/" + sm {
return true
}
}
}
return false
}
func andIP(ip, mask byte) net.IP {
inv := net.IP{}
for i, v := range ip {
inv = append(inv, mask[i]&v)
}
return inv
}
// Bigger than we need, not too big to worry about overflow
const big = 0xFFFFFF
// Decimal to integer.
// Returns number, characters consumed, success.
func dtoi(s string) (n int, i int, ok bool) {
n = 0
for i = 0; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
n = n*10 + int(s[i]-'0')
if n >= big {
return big, i, false
}
}
if i == 0 {
return 0, 0, false
}
return n, i, true
}
func mask(m string, iplen int) (net.IPMask, error) {
n, i, ok := dtoi(m)
if !ok || i != len(m) || n < 0 || n > 8*iplen {
return nil, &net.ParseError{Type: "CIDR address"}
}
return net.CIDRMask(n, 8*iplen), nil
}
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
add a comment |
-1
-1
-1
We solved this problem in our project:
isIPV4inCIDRList("35.132.199.128", string{"35.132.199.128/27"})
func isIPV4inCIDRList(ip byte, list string) bool {
for i := 0; i < 32; i++ {
sm := strconv.Itoa(i)
m, _ := mask(sm, 4)
inv := andIP(ip, byte(m))
if len(inv) == 0 {
continue
}
for _, cidr := range list {
if cidr == inv.String() + "/" + sm {
return true
}
}
}
return false
}
func andIP(ip, mask byte) net.IP {
inv := net.IP{}
for i, v := range ip {
inv = append(inv, mask[i]&v)
}
return inv
}
// Bigger than we need, not too big to worry about overflow
const big = 0xFFFFFF
// Decimal to integer.
// Returns number, characters consumed, success.
func dtoi(s string) (n int, i int, ok bool) {
n = 0
for i = 0; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
n = n*10 + int(s[i]-'0')
if n >= big {
return big, i, false
}
}
if i == 0 {
return 0, 0, false
}
return n, i, true
}
func mask(m string, iplen int) (net.IPMask, error) {
n, i, ok := dtoi(m)
if !ok || i != len(m) || n < 0 || n > 8*iplen {
return nil, &net.ParseError{Type: "CIDR address"}
}
return net.CIDRMask(n, 8*iplen), nil
}
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
We solved this problem in our project:
isIPV4inCIDRList("35.132.199.128", string{"35.132.199.128/27"})
func isIPV4inCIDRList(ip byte, list string) bool {
for i := 0; i < 32; i++ {
sm := strconv.Itoa(i)
m, _ := mask(sm, 4)
inv := andIP(ip, byte(m))
if len(inv) == 0 {
continue
}
for _, cidr := range list {
if cidr == inv.String() + "/" + sm {
return true
}
}
}
return false
}
func andIP(ip, mask byte) net.IP {
inv := net.IP{}
for i, v := range ip {
inv = append(inv, mask[i]&v)
}
return inv
}
// Bigger than we need, not too big to worry about overflow
const big = 0xFFFFFF
// Decimal to integer.
// Returns number, characters consumed, success.
func dtoi(s string) (n int, i int, ok bool) {
n = 0
for i = 0; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
n = n*10 + int(s[i]-'0')
if n >= big {
return big, i, false
}
}
if i == 0 {
return 0, 0, false
}
return n, i, true
}
func mask(m string, iplen int) (net.IPMask, error) {
n, i, ok := dtoi(m)
if !ok || i != len(m) || n < 0 || n > 8*iplen {
return nil, &net.ParseError{Type: "CIDR address"}
}
return net.CIDRMask(n, 8*iplen), nil
}
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
answered Nov 20 '18 at 16:52
Alex PliutauAlex Pliutau
14.3k2490131
14.3k2490131
add a comment |
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53397369%2ffastest-way-search-ip-in-large-ip-subnet-list-on-golang%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
convert the ip + CIDR mask to 5 bytes and store them in a uint, then use the resultant number as a map key. If you want to find which range a particular ip falls in then that would be slightly more complicated
– Vorsprung
Nov 20 '18 at 16:38
What is a "very large list"? Are you using a binary search? Are you certain the code is slow because of iterating over the list, or because you're converting every string to an ip&mask for every comparison?
– JimB
Nov 20 '18 at 16:44
at this moment in list 200k records, updated first post with code
– Rapid Code Lab
Nov 20 '18 at 16:50
You're parsing every string for every comparison. Wouldn't it make sense to parse those ahead of time first and see if that is performant enough? (It also might help to show where the bottleneck is from some real benchmarks)
– JimB
Nov 20 '18 at 16:58
1
I think a trie would be a good data structure to use here, since you're essentially doing a prefix search. I don't have a ready-made package to recommend, although github.com/derekparker/trie looks decent.
– Mark Plotnick
Nov 20 '18 at 17:02