1 (изменено: badik, 2014-02-27 11:40:09)

Тема: JScript:Быстрый поиск узла в большом XML файле

Для нормального размера XML файлов метод selectSingleNode является незаменимым.
Однако если число узлов больше 200 000 узлов  (50 000 первого  и 150 000 второго порядков) поиск при обновлении XML начинает тормозить.
Если вместо selectSingleNode использовать Object (hash массив) для хранения ключей поиска и порядковых номеров узлов скорость поиска возрастет в разы до определеного предела.

    dom = loadDom()
    r = dom.documentElement
    t = new Date()
    var o_i = {}
    var sPath = "//e"
    var oNodes = dom.selectNodes(sPath);
    for (var i = 0; i < oNodes.length; i++) {
        o_i[[e.getAttribute("i"), e.getAttribute("k"), e.getAttribute("l")].join("|")] = i
    }

    for (var j = 0; j < MaxNode * 4; j++) {
        i = Math.round(Math.random() * MaxNode)
        e = null
        var e_num = -1
        var x = [i, i % 3, i % 7].join("|")
        if (o_i[x] == null) {
            e = r.appendChild(dom.createElement("e"))
            e.setAttribute("i", i)
            e.setAttribute("k", i % 3)
            e.setAttribute("l", i % 7)
            e.setAttribute("s", "0")
        } else {
            e_num = o_i[x]
            e = r.childNodes[o_i[x]]
        }
        e.setAttribute("s", (1 * e.getAttribute("s")) + 1)
        f = e.appendChild(dom.createElement("f"))
        f.setAttribute("ii", i)
        f.setAttribute("t", j)

        o_i[[e.getAttribute("i"), e.getAttribute("k"), e.getAttribute("l")].join("|")] = e_num < 0 ? r.childNodes.length - 1 : e_num
    }

В тесте используются

  • 1.ADD - простое последовательное добавление узлов.

  • 2.selectSingle - Случайное добавление узлов поиск selectSingleNode.

  • 3.selectObject Случайноe добавление через Object hash массив.

  • 4.Скорость заполнения hash массив XML полученный в 3 тесте.


+ Тест
var aCount = [1000, 5000, 10000, 25000, 40000, 50000, 75000, 100000, 150000, 200000]
for (var z = 0; z < aCount.length; z++) {
    var MaxNode = aCount[z]
    WScript.Echo("узлов:" + MaxNode)

    dom = loadDom()
    r = dom.documentElement
    t = new Date()
    for (var i = 0; i < MaxNode; i++) {
        e = r.appendChild(dom.createElement("e"))
        e.setAttribute("i", i)
        e.setAttribute("k", i % 3)
        e.setAttribute("l", i % 7)
        e.setAttribute("s", "0")

        for (var j = 0; j < 4; j++) {
            e.setAttribute("s", (x = 1 * e.getAttribute("s")) + 1)
            f = e.appendChild(dom.createElement("f"))
            f.setAttribute("ii", i)
            f.setAttribute("t", j)
        }

    }
    WScript.Echo("1.ADD         :" + time(t) + lNode(dom))
    if (MaxNode < 80000) {
        dom = loadDom()
        r = dom.documentElement
        t = new Date()

        for (var j = 0; j < MaxNode * 4; j++) {
            i = Math.round(Math.random() * MaxNode)
            var sPath = "/root/e[@i='" + i + "']" + "[@k='" + i % 3 + "']" + "[@l='" + i % 7 + "']"
            var e = dom.selectSingleNode(sPath)
            if (e == null) {
                e = r.appendChild(dom.createElement("e"))
                e.setAttribute("i", i)
                e.setAttribute("k", i % 3)
                e.setAttribute("l", i % 7)
                e.setAttribute("s", "0")
            }
            e.setAttribute("s", (1 * e.getAttribute("s")) + 1)
            f = e.appendChild(dom.createElement("f"))
            f.setAttribute("ii", i)
            f.setAttribute("t", j)
        }
        WScript.Echo("2.selectSingle:" + time(t) + lNode(dom))
    }
    dom = loadDom()
    r = dom.documentElement
    t = new Date()
    var o_i = {}

    for (var j = 0; j < MaxNode * 4; j++) {
        i = Math.round(Math.random() * MaxNode)
        e = null
        var e_num = -1
        var x = [i, i % 3, i % 7].join("|")
        if (o_i[x] == null) {
            e = r.appendChild(dom.createElement("e"))
            e.setAttribute("i", i)
            e.setAttribute("k", i % 3)
            e.setAttribute("l", i % 7)
            e.setAttribute("s", "0")
        } else {
            e_num = o_i[x]
            e = r.childNodes[o_i[x]]
        }

        e.setAttribute("s", (1 * e.getAttribute("s")) + 1)
        f = e.appendChild(dom.createElement("f"))
        f.setAttribute("ii", i)
        f.setAttribute("t", j)

        o_i[[e.getAttribute("i"), e.getAttribute("k"), e.getAttribute("l")].join("|")] = e_num < 0 ? r.childNodes.length - 1 : e_num
    }
    WScript.Echo("3.selectObject:" + time(t) + lNode(dom))

    t = new Date()
    var o_i = {}
    var sPath = "//e"

    var oNodes = dom.selectNodes(sPath);

    for (var i = 0; i < oNodes.length; i++) {
        o_i[[e.getAttribute("i"), e.getAttribute("k"), e.getAttribute("l")].join("|")] = i
    }
    WScript.Echo("4.Load  Object:" + time(t))

    WScript.Echo("")
}

function loadDom() {
    var dom
    dom = new ActiveXObject("msxml2.DOMDocument");
    dom.async = false;
    dom.validateOnParse = false;
    dom.resolveExternals = false;
    dom.appendChild(dom.createProcessingInstruction("xml", "version='1.0' encoding='windows-1251'"))
    dom.appendChild(dom.createElement("root"))
    dom.setProperty("SelectionLanguage", "XPath")
    return dom
}

function time(t) {
    var tt = new Date()
    var d = (new Date(tt - t))
    d.setMinutes(d.getMinutes() + d.getTimezoneOffset())
    return ("" + r(d.getHours()) + ":" + r(d.getMinutes()) + ":" + r(d.getSeconds()) + "." + d.getMilliseconds())

        function r(d) {
            var s = "00" + d
            return (s.substr(s.length - 2, 2))
        }
}

function lNode(dom) {
    var sPath = "//e"
    var oNodes = dom.selectNodes(sPath);
    return (" узлов:" + oNodes.length)
}
+ Результаты теста

Результаты теста

узлов:1000
1.ADD         :00:00:00.47 узлов:1000
2.selectSingle:00:00:00.890 узлов:982
3.selectObject:00:00:00.141 узлов:988
4.Load  Object:00:00:00.0

узлов:5000
1.ADD         :00:00:00.265 узлов:5000
2.selectSingle:00:00:19.392 узлов:4907
3.selectObject:00:00:01.109 узлов:4902
4.Load  Object:00:00:00.31

узлов:10000
1.ADD         :00:00:00.516 узлов:10000
2.selectSingle:00:01:19.392 узлов:9806
3.selectObject:00:00:03.313 узлов:9831
4.Load  Object:00:00:00.94

узлов:25000
1.ADD         :00:00:01.468 узлов:25000
2.selectSingle:00:09:16.983 узлов:24590
3.selectObject:00:00:19.422 узлов:24583
4.Load  Object:00:00:00.219

узлов:40000
1.ADD         :00:00:02.657 узлов:40000
2.selectSingle:00:24:22.365 узлов:39251
3.selectObject:00:00:58.658 узлов:39271
4.Load  Object:00:00:00.406

узлов:50000
1.ADD         :00:00:03.453 узлов:50000
2.selectSingle:00:38:27.12 узлов:49079
3.selectObject:00:01:39.159 узлов:49091
4.Load  Object:00:00:00.609

узлов:75000
1.ADD         :00:00:06.157 узлов:75000
2.selectSingle:01:27:43.805 узлов:73651
3.selectObject:00:04:27.100 узлов:73616
4.Load  Object:00:00:00.812

узлов:100000
1.ADD         :00:00:09.438 узлов:100000
3.selectObject:00:09:00.608 узлов:98126
4.Load  Object:00:00:01.172

узлов:150000
1.ADD         :00:00:17.891 узлов:150000
3.selectObject:00:23:03.441 узлов:147339
4.Load  Object:00:00:01.672

узлов:200000
1.ADD         :00:00:28.860 узлов:200000
3.selectObject:00:44:33.89 узлов:196309
4.Load  Object:00:00:02.547

2

Re: JScript:Быстрый поиск узла в большом XML файле

Не ожидано нашел дополнительное ускорение поиска узлов в обновляемом XML файле.
Теперь реальный скрипт (написанный в 2006г) стал  работать в 30 раз быстрее (с 110 минут до 3.5 минут)
Примерный Алгоритм:
1.Читаем XML файл
2. Заполняем
     Объект  значениями ключей и порядковым номером узла o_i[хэш]=i
     Создаем массив куда копируем удаленные из XML узлы

a_i[i]=  oNodes[i].parentNode.removeChild(oNodes[i])

3. Выполняем массовую обработку
4. Востанавливаем XML файл

  for (var j = 0; j < a_i.length; j++) {
    r.appendChild(a_i[j])
  }

5. Сохраняем файл

+ Тест2
var fso = new ActiveXObject("Scripting.FileSystemObject")
var logFile = fso.OpenTextFile("test_2.log", 8, true)

var aStep = [10, 15, 25, 50, 150, 250, 100, 100]
var MaxNode = 0
for (var z = 0; z < aStep.length; z++) {
  MaxNode += (aStep[z] * 1000)
  alert("узлов:" + MaxNode)
  tt = new Date()
  t = new Date()
  dom = loadDom("test.xml")

  alert("1. Read XML         :" + time(t))

  r = dom.documentElement
  t = new Date()
  var o_i = {}
  var a_i = []
  var sPath = "//e"

  t = new Date()
  var oNodes = dom.selectNodes(sPath);

  for (var i = 0; i < oNodes.length; i++) {
    var e = oNodes[i]
    o_i[[e.getAttribute("i"), e.getAttribute("k"), e.getAttribute("l")].join("|")] = i
    a_i[i] = oNodes[i].parentNode.removeChild(oNodes[i]);

  }
  alert("2. Create index Node:" + time(t))

  for (var j = 0; j < MaxNode * 4; j++) {
    i = Math.round(Math.random() * MaxNode)
    e = null
    var e_num = -1
    var x = [i, i % 3, i % 7].join("|")
    if (o_i[x] == null) {
      o_i[x] = a_i.length
      e = dom.createElement("e")
      e.setAttribute("i", i)
      e.setAttribute("k", i % 3)
      e.setAttribute("l", i % 7)
      e.setAttribute("s", "0")
      a_i[a_i.length] = e
    }
    e_num = o_i[x]
    e = a_i[o_i[x]]

    e.setAttribute("s", (1 * e.getAttribute("s")) + 1)
    f = e.appendChild(dom.createElement("f"))
    f.setAttribute("ii", i)
    f.setAttribute("t", j)

    o_i[[e.getAttribute("i"), e.getAttribute("k"), e.getAttribute("l")].join("|")] = e_num < 0 ? r.childNodes.length - 1 : e_num
  }
  alert("3. Append Node      :" + time(t))
  t = new Date()

  for (var j = 0; j < a_i.length; j++) {
    r.appendChild(a_i[j])
  }

  alert("4. Create XML       :" + time(t) + lNode(dom))

  dom.save("test.xml")
  alert("5. Save XML         :" + time(t))
  alert("               total:" + time(tt))
  alert("")

  fso.CopyFile("test.xml", "t." + MaxNode + ".xml")

}

function alert(x) {
  WScript.Echo(x)
  logFile.WriteLine(x)
}

function loadDom(xFile) {
  var dom
  dom = new ActiveXObject("msxml2.DOMDocument.6.0");
  dom.async = false;
  dom.validateOnParse = false;
  dom.resolveExternals = false;
  if (!dom.load(xFile)) {
    dom.appendChild(dom.createProcessingInstruction("xml", "version='1.0' encoding='windows-1251'"))
    dom.appendChild(dom.createElement("root"))
  }
  dom.setProperty("SelectionLanguage", "XPath")
  return dom
}

function time(t) {
  var tt = new Date()
  var d = (new Date(tt - t))
  d.setMinutes(d.getMinutes() + d.getTimezoneOffset())
  return ("" + r(d.getHours()) + ":" + r(d.getMinutes()) + ":" + r(d.getSeconds()) + "." + d.getMilliseconds())

    function r(d) {
      var s = "00" + d
      return (s.substr(s.length - 2, 2))
    }
}

function lNode(dom) {
  var sPath = "//e"
  var oNodes = dom.selectNodes(sPath);
  return (" узлов:" + oNodes.length)
}
+ Результаты теста2

узлов:10000
1. Read XML         :00:00:00.0
2. Create index Node:00:00:00.0
3. Append Node      :00:00:00.985
4. Create XML       :00:00:00.15 узлов:9815
5. Save XML         :00:00:00.125
               total:00:00:01.110

узлов:25000
1. Read XML         :00:00:00.93
2. Create index Node:00:00:00.157
3. Append Node      :00:00:02.719
4. Create XML       :00:00:00.63 узлов:24743
5. Save XML         :00:00:00.485
               total:00:00:03.297

узлов:50000
1. Read XML         :00:00:00.359
2. Create index Node:00:00:00.406
3. Append Node      :00:00:05.938
4. Create XML       :00:00:00.125 узлов:49534
5. Save XML         :00:00:01.62
               total:00:00:07.359

узлов:100000
1. Read XML         :00:00:01.281
2. Create index Node:00:00:00.844
3. Append Node      :00:00:13.641
4. Create XML       :00:00:00.266 узлов:99077
5. Save XML         :00:00:01.891
               total:00:00:16.813

узлов:250000
1. Read XML         :00:00:05.47
2. Create index Node:00:00:01.765
3. Append Node      :00:00:39.813
4. Create XML       :00:00:00.641 узлов:247235
5. Save XML         :00:00:03.531
               total:00:00:48.391

узлов:500000
1. Read XML         :00:00:27.32
2. Create index Node:00:00:04.672
3. Append Node      :00:01:43.268
4. Create XML       :00:00:01.344 узлов:495284
5. Save XML         :00:00:05.656
               total:00:02:15.971

узлов:600000
1. Read XML         :00:01:56.456
2. Create index Node:00:00:09.765
3. Append Node      :00:02:31.862
4. Create XML       :00:00:01.750 узлов:598139
5. Save XML         :00:00:08.672
               total:00:04:36.990

узлов:700000
1. Read XML         :00:01:09.408
2. Create index Node:00:00:00.0  -- Скрипт не смог считать узлы dom.selectNodes(sPath) вернул 0 Узлов