long ruleset perfomance issue

[<anton@web-sat.com>]

Hello,
I need to mark packets going through a linux router with iptables for some 4500 ip addresses(to use with tc bandwidth shaping filters).
This list needs to be updated every 10 minutes.
So i made a shell script file looking like:

/usr/local/sbin/iptables -F 
/usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.1 -j MARK --set-mark 1
/usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.3 -j MARK --set-mark 2
/usr/local/sbin/iptables -A FORWARD -t mangle -d 1.1.1.2 -j MARK --set-mark 1
and so on for 4500 times.

When i run this script on Xeon 2.4ghz cpu it takes 2-3 minutes real time with 100% cpu load to process.
During this time server becomes unusable. 
Is there any way to make it run faster, like optimizing ruleset or trying a different approach?
I have tried to search on this issue but was not successful.

Any input is greatly appreciatred.

Thank you,
Anton